枚举例题：熄灯问题 反思

代码：

#include <iostream>

using namespace std;

//block代表初始状态，亮为1，不亮为0.ans代表开关是否被按下，扩大一层，默认外圈都是熄灭的
//注意全局变量不初始化的话会自动初始化为0，所以不用手动去初始化
int block[7][8],ans[7][8];

//判断当前解是否可行
bool check_ans(){
    for(int i=2;i<=6;++i){
        for(int j=1;j<=6;++j){
            //每一个按钮是否按下取决于它上面一个按钮的现状
            ans[i][j]=block[i-1][j]^ans[i-1][j-1]^ans[i-1][j+1]^ans[i-2][j]^ans[i-1][j];
        }
    }
    //如果最后一行也全部熄灭，说明这种方法可行
    for(int j=1;j<=6;++j){
        //新加入的最底下一行如果需要按下，就说明原来的最后一行没有熄灭，不满足题意
        if(ans[6][j]==1){
            return false;
        }
    }
    return true;

}

//运用枚举来找到解并输出
void solve(){
    //只用枚举第一行的状态，要用六重循环？
    //好吧其实只要这样，利用位运算的思想，就可以遍历所有的情况

    for(int i=0;i<(1<<6);++i){
        int k=i;
        for(int j=1;j<=6;++j){
            ans[1][j]=k%2;
            k/=2;
        }
        if(check_ans())
            break;
    }
    //输出是否按下的情况
    for(int i=1;i<=5;++i){
        for(int j=1;j<=6;++j){
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
}

int main()
{
    //输入初始状态
    for(int i=1;i<=5;++i){
        for(int j=1;j<=6;++j){
            cin>>block[i][j];
        }
    }
    //调用方法直接得到答案
    solve();
    return 0;
}
//本题还有更强的利用位运算的方法，有信心时去看mooc

1.这里有一个很关键的点是如何判断一个灯是否需要被按下。
用到异或。两次相同的操作可以抵消，两次不同的操作可以改变状态，满足异或的使用条件。

2.算法思想是枚举，总体思路代码中有所体现，此问题只用枚举第一行（或第一列），就可以推出剩下行（列）的所有按法，枚举第一行（列）的所有情况，然后判断是否可以把所有的灯熄灭即可。
3.这里有一个比较通用的思想就是使用函数，一个判断函数，一个用于枚举输出结果的函数，在后着中调用前者，可以实现枚举+判断，主函数中直接调用后者即可，使主函数简洁。