费解的开关

题目描述

你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“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(leq) n (leq) 500

输入样例

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例

3
2
-1

思路

我们先假定第一行的开关不被按，这样的话要使第一行的某个关着的灯打开，应当按下其同一列中下一行的灯。当稳定好第1行的灯后，要想保持第一行的灯的状态不再被改变，第2行的灯也不能再按下了。如果想要使第2行的相应的关着的灯打开，我们需要按下第3行中同列相应的灯。剩下的行数依次类推。到第n行时，为了使第n-1行的灯的状态不再被改变我们不能再按下第n行的灯。这样，判断此时所有的灯是否全部是打开的状态的话我们只需要判断第n行的灯的状态是否全部是打开的状态。因为我们已经保证了第1~n-1行的灯全部是打开的状态。

而实际上，第一行的灯也是可以按的，根据每个灯按与不按的选择。我们共有(2^5)=32种方案。当按完第一行的灯后我们再来考虑上面的思路就可以了。而且应当注意的是，每一个位置顶多只会操作一次。因为如果操作两次的话，相当于不操作，必然是不满足最优解。跟据之前学的状态压缩的知识，我们可以使用枚举变量k的2进制表示形式中的1/0来记录第1行中相应位置的灯的按/不按。
eg：k=23=({(10111)}_2)——>按/按/按/不按/按(注意:k的二进制形式是从右往左开始计算的)

C++代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
char mp[7][7];
int dx[5] = { 0,0,-1,1,0 }, dy[5] = { 1,-1,0,0,0 };//方位数组
void turn(int x, int y)//使坐标(x,y)周围的灯的状态改变
{
	for (int i = 0;i < 5;i++)
	{
		int a = x + dx[i];
		int b = y + dy[i];
		if (a >= 0 && a < 5 && b >= 0 && b < 5)
			mp[a][b] = '0' + '1' - mp[a][b];//使满足条件的灯的状态改变
	}
}
int work()
{
	int res = INF;
	for (int k = 0;k < (1 << 5);k++)//第0行中共有5个灯，每个灯都有按与不按两种选择，对应于k的2进制表示就是每位上的1/0。所以最后共有32种情况。我们将第一行所有按的情况都枚举一下，在第一行确定的情况下，剩下的行数，按与不按也就可以确定了
	{
		char re[7][7];
		int ans = 0;
		memcpy(re, mp, sizeof (mp));//把mp中的信息拷贝到re中
		for (int i = 0;i < 5;i++)
			if (k >> i & 1)
			{
				ans++;
				turn(0, i);//根据k的2进制表示信息我们可以知道需要将(0,i)上的灯按一下
			}
		for (int i = 0;i < 4;i++)
		{
			for (int j = 0;j < 5;j++)
				if (mp[i][j] == '0')
				{
					ans++;
					turn(i + 1, j);
				}
		}
		bool is_sucessful = true;//判断最后一行的灯是不是全部都是亮的，如果是的话就表示我们枚举的这个方案是成功的
		for (int i = 0;i < 5;i++)
			if (mp[4][i] == '0')
			{
				is_sucessful = false;
				break;
			}
		if (is_sucessful)//如果该方案成功的话我们需要维护一下最小值便于最后输出方案最小值
			res = min(res, ans);
		memcpy(mp, re, sizeof (mp));//再把mp中灯的开关情况恢复，便于接下来对k的枚举
	}
	if(res>6)
	   res=-1;
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	while (n--)
	{
		for (int i = 0;i < 5;i++)
		{
			for (int j = 0;j < 5;j++)
				cin >> mp[i][j];
		}
		cout << work() << endl;
	}
	return 0;
}

逆向思维+bfs预处理的C++代码

//运用逆向思维，我们可以从灯全亮的状态开始bfs走6步，记录下所有能到达的状态所需步数，相当于预处理，对于每组数据直接输出答案即可。
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
queue<int> q;
map<int,int> ans; //注意要用map，如果开ans[1<<25]会MLE，毕竟很多状态是没用的
int T;
 
inline int flip(int x,int i) { //将以i为中心的上下左右反转，注意边界判断
    x^=(1<<i);
    if (i%5!=4) x^=(1<<(i+1));
    if (i%5) x^=(1<<(i-1));
    if (i>4) x^=(1<<(i-5));
    if (i<20) x^=(1<<(i+5));
    return x;
}
 
int main() {
    scanf("%d",&T);
     
    q.push((1<<25)-1),ans[(1<<25)-1]=1; //全亮的状态
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        if (ans[x]==7) break; //只走6步
        for (int i=0,y; i<25; i++) //枚举反转哪一盏灯
            if (ans[y=flip(x,i)]==0)
                q.push(y),ans[y]=ans[x]+1;
    }
     
    while(T--) {
        int y=0;
        for (int i=0,x; i<5; i++)
            for (int j=0; j<5; j++)
                scanf("%1d",&x),y+=x<<(i*5+j); //把矩阵看成二进制数压缩到y里去（当然也可以用数组存储）
        printf("%d
",ans[y]? ans[y]-1:-1);
    }
}