[数据结构与算法]AcWing 95. 费解的开关 (递归&位运算 详解)

你玩过“拉灯”游戏吗？

2525?盏灯排成一个?5×55×5?的方形。

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

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

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

我们用数字?11?表示一盏开着的灯，用数字?00?表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011

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

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

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

输入格式

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

以下若干行数据分为?nn?组，每组数据有?55?行，每行?55?个字符。

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

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

输出格式

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

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

数据范围

0<n≤5000<n≤500

输入样例：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

3
2
-1

解题思路：根据第一行已有的数据 我们可以有2的5次方次按法 (选择按还是不按)，然后根据我们的按法变化的数据; 从头开始去进行查询、改变灯的状态，因为你每次操作肯定会把前四行的灯都弄亮，我们的第五行的数据就没有办法再进行变化了，所以我们最后只需要判断最后一行灯是否全亮。如果可以完成的话 我们只需要把完成的次数存下来，存最小的数就行了。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

具体可以看代码里面的注释。
memcpy 可以用来进行原数据备份 然后操作e 每进行完一次开关的按法之后再还原回去 再操作

AC

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 6;

char e[N][N], backup[N][N];
int dx[5]={-1, 0, 1, 0, 0}, dy[5]={0, 1, 0, -1, 0};

void turn(int x, int y) //变状态 
{
	for (int i = 0; i < 5; i ++)
	{
		int a = x + dx[i], b = y + dy[i];
		if (a < 0 || a >= 5 || b < 0 || b>= 5)	continue; //越界 忽略 
		e[a][b] ^= 1;  //不同为1 相同为0 
	}
}

int main()
{
	int t;
	cin >> t;
	while(t --)
	{
		for (int i = 0; i < 5; i ++)
			cin >> e[i];
	
		int res = 10;
		for (int op = 0; op < 32; op ++) //第一行的灯可以有2^5种开关法 去递归所有的按法  
		{
			memcpy(backup, e, sizeof e); //原数据备份 然后操作e 每进行完一次开关的按法之后再还原回去 再操作
			int step = 0;
			for (int i = 0;i < 5; i ++)
				//与运算 同时为1 结果才为1 
				if (op >> i & 1) //二进制下第i位为1表示按了第一行的第i个位置灯的开关  
				{
					step ++;
					turn(0, i); //因为我们按了这个位置 所以我们要去它附近的灯变化一下 
				} 
			//第一行按完之后 再根据按完后的数据 去从头开始检查 
			for (int i = 0; i < 4 ;i++) 
				for (int j = 0; j < 5; j++)
					if (e[i][j] == '0') //当前行灯i j是暗的时候 以这个灯的下一行i j+1去改变灯 
					{
						step++;
						turn(i + 1, j);
					}
			
			bool close = false;
			// 因为我们前面已经把前四行灯暗的 都调亮了 
			//所以最后判断的时候只需要看最后一行的灯是否全是亮的就行了 
			for (int i = 0; i < 5; i ++) 
				if (e[4][i] == '0')
					close = true;
					
			if (!close) res = min(res, step);
			memcpy(e, backup, sizeof e);
		}
		
		if (res > 6)
			res = -1;
		cout << res << endl;
	}
	return 0;
}