蓝桥杯算法提高VIP-开灯游戏-题解-DFS模板题(C++代码)

/*
题目描述
有9盏灯与9个开关，编号都是1~9。
每个开关能控制若干盏灯，按下一次会改变其控制的灯的状态(亮的变成不亮，不亮变成亮的)。
具体如下：
第一个开关控制第二，第四盏灯；
第二个开关控制第一，第三，第五盏灯；
第三个开关控制第二，第六盏灯；
第四个开关控制第一，第五，第七盏灯；
第五个开关控制第二，第四，第六，第八盏灯；
第六个开关控制第三，第五，第九盏灯；
第七个开关控制第四，第八盏灯；
第八个开关控制第五，第七，第九盏灯；
第九个开关控制第六，第八盏灯。
开始时所有灯都是熄灭的，开关是关闭着的。要求按下若干开关后，使得只有4盏灯亮着。
输入
无
输出
输出所有可能的方案，每行一个方案，每一行有9个字符，从左往右第i个字符表示第i个开关的状态(" 0" 表示关闭，" 1" 表示打开)，按字典序输出。下面的样例输出只是部分方案。 
样例输入
无
样例输出
000001011 
000001110 
000001111 
*/
/*
重点：
思路： 
    dfs 按位深搜 
*/
#include<iostream>
using namespace std;
int a[10];            // 记录每个按钮的状态 
int light[10];        // 记录灯的开关 状态 
void f(int i){
    //修改第 i 栈灯的状态
    if(light[i] == 0)    light[i] = 1;
    else light[i] = 0; 
}
bool check(){
    int cnt = 0;
    for(int i = 1;i <= 9;++i )
        if(light[i])
            ++cnt;
    if(cnt == 4)    return true;
    else return false;    
}
void dfs(int s){
    // 当前走到第 s 栈灯
    //判断终点 
    if(s == 10){
        if(check()){
            for(int i = 1;i <= 9;++i)
            cout<<a[i];
        cout<<endl;
        }
        return ;
    } 
    // 对所有可走点 dfs 
    if(s == 1){
        // 0  状态，什么也不做 
        a[s] = 0;
        dfs(s+1);
        // 1
        a[s] = 1;
        f(2);
        f(4);
        dfs(s+1);
        // 状态恢复 
        f(2);
        f(4);
    }
    else if(s == 2){
        // 0  
        a[s] = 0;
        dfs(s+1);
        // 1
        a[s] = 1;
        f(1);
        f(3);
        f(5);
        dfs(s+1);
    // 状态恢复 
        f(1);
        f(3);
        f(5);
    }
    else if(s == 3){
        // 0  
        a[s] = 0;
        dfs(s+1);
        // 1
        a[s] = 1;
        f(2);
        f(6);
        dfs(s+1);
    // 状态恢复 
        f(2);
        f(6);
    }
    else if(s == 4){
        // 0  
        a[s] = 0;
        dfs(s+1);
        // 1
        a[s] = 1;
        f(1);
        f(5);
        f(7);
        dfs(s+1);
    // 状态恢复 
        f(1);
        f(5);
        f(7);
    }
    else if(s == 5){
        // 0  
        a[s] = 0;
        dfs(s+1);
        // 1
        a[s] = 1;
        f(2);
        f(4);
        f(6);
        f(8);
        dfs(s+1);
    // 状态恢复 
        f(2);
        f(4);
        f(6);
        f(8);
    }
    else if(s == 6){
        // 0  
        a[s] = 0;
        dfs(s+1);
        // 1
        a[s] = 1;
        f(3);
        f(5);
        f(9);
        dfs(s+1);
    // 状态恢复 
        f(3);
        f(5);
        f(9);
    }
    else if(s == 7){
        // 0  
        a[s] = 0;
        dfs(s+1);
        // 1
        a[s] = 1;
        f(4);
        f(8);
        dfs(s+1);
    // 状态恢复 
        f(4);
        f(8);
    }
    else if(s == 8){
        // 0  
        a[s] = 0;
        dfs(s+1);
        // 1
        a[s] = 1;
        f(5);
        f(7);
        f(9);
        dfs(s+1);
    // 状态恢复 
        f(5);
        f(7);
        f(9);
    }    
    else if(s == 9){
        // 0  
        a[s] = 0;
        dfs(s+1);
        // 1
        a[s] = 1;
        f(6);
        f(8);
        dfs(s+1);
    // 状态恢复 
        f(6);
        f(8);
    }    
}
int main(){
    dfs(1);
    return 0;
}