有一个由按钮组成的矩阵，其中每行有6个按钮，共五行
每个按钮的位置上有一盏灯
当按下一个按钮后，该按钮以及周围位置（上下左右）的灯都会改变状态
如果灯原来是点亮的，就会被熄灭
如果灯原来是熄灭的，则会被点亮
- 在矩阵角上的按钮改变3盏灯的状态
- 在矩阵边上的按钮改变4盏灯的状态
- 其他的按钮改变5盏灯的状态
- 与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果
- 给定矩阵中每盏灯的初始状态，求一种按按钮方案，使得所有的灯都熄灭
输入 :
- 第一行是一个正整数N，表示需要解决的案例数
- 每个案例由5行组成，每一行包括6个数字
- 这些数字以空格隔开，可以是0或1
- 0表示灯的初始状态是熄灭的
- 1表示灯的初始状态是点亮的
输出 :
- 对每个案例，首先输出一行
输出字符串 “PUZZLE #m”，其中 m 是该案例的序 号- 接着按照该案例的输入格式出5行
- 1表示需要把对应的按钮按下
- 0表示不需要按对应的按钮
- 每个数字以一个空格隔开
解题分析
第一想法：枚举所有可能的按钮（开关）状态，对每一个状态计算一下最后灯的情况，看是否都熄灭
——每个按钮有两种状态（按下或不按下）
——一共有30个开关，那么状态数为，太多，会运行超时
那么，如何减少枚举数目呢？
基本思路：如果存在某个局部，一旦这个局部的状态被确定，那么剩余其他部分的状态只能是确定的一种，或者不多的n种，那么就只需要枚举这个局部的状态即可
经过观察发现，第一行就是这样的一个“局部”
因为第一行的各个开关状态确定的情况下，这些开关作用过后，将导致第一行某些灯是亮的，某些灯是灭的。
要熄灭第一行某个亮着的灯（假设位于第i列），那么唯一的办法就是按下第二行第i列的开关
{因为第一行的开关已经用过了，而第三行及其后的开关不会影响的第一行}
为了使第一行的灯全部熄灭，第二行的合理开关状态就是唯一的。
#include<memory>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
char oriLights[5];//代表一行的灯，一共五行
char lights[5];
char result[5];
int GetBit(char c, int i)
{
return(c>>i ) & 1;//给c右移i位与1进行与操作
}
void SetBit(char &c,int i,int v)//设置字符的第i位为v
{
if(v){
c|=(1<<i);//把c的第i位变成1 ，即v=1
}
else
c &= ~(1<<i);//“~”是取反操作，将c的第i位变为1，即v=1
}
void FlipBit(char & c,int i)//设置翻转
{
c ^=(1<<i);//异或 ，将c的第i位翻转
}
void OutputResult(int t, char result[])
{
cout<<"PUZZLE #"<< t <<endl;
for(int i=0;i<5;++i){
for(int j=0;j<6;++j){
cout<<GetBit(result[i],j);
if(j<5)
cout<<" ";
}
cout<<endl;
}
}
int main()
{
int T;
cin>>T;
for(int t=1;t<=T;++t){
for(int i=0;i<5;++i){//i行
for(int j=0;j<6;++j){//j列
int s;
cin>>s;//s为第i行j列的灯的状态，只有0,1两种
SetBit(oriLights[i],j,s);
}
for(int n=0;n<64;++n){//枚举第一行灯的开关状态因为第一行有六个灯，所有情况共有64种，0-63
int switchs=n;//当前行的灯的状态
memcpy(lights,oriLights,sizeof(oriLights));
for(int i=0;i<5;++i){
result[i]=switchs;
for(int j=0;j<6;j++){
if(GetBit(switchs,j)) {
if(j>0)
FlipBit(lights[i],j-1);
FlipBit(lights[i],j);
if(j<5)
FlipBit(lights[i],j+1);
}
}
if(i<5)
lights[i+1] ^=switchs;
switchs=lights[i];
}
if(lights[4]==0) {
OutputResult(t,result);
break;
}
}
}
return 0;
}
}