AcWing 95.费解的开关

链接：https://www.acwing.com/problem/content/97/
题目：
你玩过“拉灯”游戏吗？

25 盏灯排成一个 5×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

输入格式
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式
一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 ?1。

数据范围
0 输入样例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例：

3
2
-1

思路：
假设从第一行到最后一行枚举，可以发现当枚举到第二行时，第一行已经不可以再改变，这时只有第二行能改变第一行的状态。而如果要保证第一行全亮的话，第一行熄灭的灯泡，在第二行对应的灯泡必须改变状态，而第一行已经亮起的灯泡，对应的第二行的灯泡此时一定不能改变状态。也就是说第一行确定的同时第二行也确定了，随之第三行第四行都已经确定。

那么思路就可以简化成：枚举第一行的状态（也就是2^5=32种状态，可以用int从0到31，转化为2进制时，每一位对应是否改变灯泡（1为改变，0为不变）），然后模拟这种情况，查看最后一行是否存在熄灭的灯泡，如果没有，就记下此时的操作步数，最后求出所有情况的最小步数，再输出就ok了。

题解：

#include
using namespace std;

const int N=6;
char g[N][N],backup[N][N];
int dx[5]={-1,0,1,0,0};
int dy[5]={0,1,0,-1,0};  //-1,0   0,1   1,0   0,-1   0,0

void change(int x,int y)
{
	for(int i=0;i<5;i++)
	{
		int a=x+dx[i],b=y+dy[i];
		if(a<0||a>4||b<0||b>4)   //坐标越界，直接忽略 
			continue;
		g[a][b]^=1;     //'0'的值是48，也就是110000，110000^1=110001
						//'1'的值是49，也就是110001，110001^1=110000
						//正好可以实现'0'和'1'的互相转换 
	}
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		for(int i=0; i<5; i++) //输入灯的状态,每一行作为一个字符串输入 
			cin>>g[i];
		int res=10;
		for(int op=0; op<32; op++) //0-31代表第一行灯泡的32种状态
		{
			int step=0;
			memcpy(backup,g,sizeof g);  //备份 
			for(int i=0;i<5;i++)
				if(op>>i&1)      //转化为二进制，也就是第一行灯泡的状态 
				{
					step++;
					change(0,i);
				}
			for(int i=0;i<4;i++) //从第一行到第四行模拟 
			{
				for(int j=0;j<5;j++)
					if(g[i][j]=='0')
					{
						step++;
						change(i+1,j);
					}
			}  
			bool dark=false;   //检查最后一行是否全亮 
			for(int i=0;i<5;i++)   
				if(g[4][i]=='0')
					dark=true;
			if(!dark) res=min(res,step); //如果全亮，则比较并记录 
			memcpy(g,backup,sizeof g);//备份回去 
		}
		if(res>6) res=-1;
		cout<