蓝桥杯算法提高VIP-开灯游戏 （C++代码）

解题思路:dfs回溯

注意事项:

参考代码:

#include<iostream>
using namespace std;
int a[10], b[10];
int num;
void kongzhi(int x)
{
    if(a[x] == 0){
        a[x] = 1;
    }
    else{
        a[x] = 0;
    }
}
void kaiguan(int x)
{
    switch(x){
        case 1:kongzhi(2),kongzhi(4);break;
        case 2:kongzhi(1),kongzhi(3),kongzhi(5);break;
        case 3:kongzhi(2),kongzhi(6);break;
        case 4:kongzhi(1),kongzhi(5),kongzhi(7);break;
        case 5:kongzhi(2),kongzhi(4),kongzhi(6),kongzhi(8);break;
        case 6:kongzhi(3),kongzhi(5),kongzhi(9);break;
        case 7:kongzhi(4),kongzhi(8);break;
        case 8:kongzhi(5),kongzhi(7),kongzhi(9);break;
        case 9:kongzhi(6),kongzhi(8);break;
    };
}
void dfs(int x)
{
    if(x == 9){
        num = 0;
        for(int i = 1; i <=9; i++){
            if(a[i] == 1){
                num++;
            }
        }
        if(num == 4){
            for(int i = 0; i < 9; i++){
                cout << b[i];
            }
            cout << endl;
        }
        return;
    }
    else{
       for(int i = 0; i < 2; i++){
         b[x] = i;
         if(i == 1){
             kaiguan(x+1);
         }
         dfs(x+1);
         if(i == 1){
             kaiguan(x+1);
         }
       }
    }
}
int main()
{
    dfs(0);
    return 0;
}