【阶段1】费解的开关（二进制压缩从而枚举状态+学会解读题目）

【题意】

你玩过“拉灯”游戏吗？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<n≤500

【输入样例】

3

00111

01011

10001

11010

11100

11101

11101

11110

11111

11111

01111

11111

11111

11111

11111

【输出样例】

3

2

-1

思路分析：

这道题看似是深搜，实则不是。

这种题要善于找突破口，这道题的突破口——我们发现：如果有一行固定了（也就是不能动这一行的任何一个开关）如果当前这一行有关着的灯，那么我们只能动下一行对应位置的开关从而把这盏灯打开。而下一行的开关也不能随便乱动，因为如果它动了的灯上一行的对应位置是开着的，那它就把原来开着的灯给关了。

根据上述情况我们可以得出一个结论——如果第一行的按法固定了，那么整个局面的按法也固定了。

所以我们就知需要枚举出第一行的按法（注意是按法不是情况，因为情况的无法枚举的）才以此判断整个局面的按法就好了。

而枚举，我们不用5重for循环，首先不好看，其次很麻烦。我们直接用五位的二进制数，每个数位的0、1对应着第一行的对应灯按或不按。五位的二进制数就是0~31，所以直接for （0~31·）就好了

这里我们又一次领略了二进制的美妙，它不单止可以压缩状态，而且可以枚举状态

附上代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
	char c=getchar();int f=1,s=0;
	while(c<'0' || '9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c && c<='9'){s=s*10+c-'0';c=getchar();}
	return f*s;
}
bool map[6][6],mapc[6][6];
int mapz[6];
inline int change(int num)
{
	int i=1,step=0;
	while(num)
	{
		if(num&1)
		{
			map[1][i]^=1;
			if(1<=i-1)map[1][i-1]^=1;
			if(i+1<=5)map[1][i+1]^=1;
			map[2][i]^=1;
			step++;
		}
		num>>=1;
		i++;
	}
	return step;
}
inline void gai(int x,int y)
{
	map[x][y]^=1;
	if(1<=x-1)map[x-1][y]^=1;
	if(x+1<=5)map[x+1][y]^=1;
	if(1<=y-1)map[x][y-1]^=1;
	if(y+1<=5)map[x][y+1]^=1;
}
int ans;
inline int mymin(int x,int y){return x<y?x:y;}
inline void dfs(int n,int step)
{
	if(step>=ans)return ;
	if(n==6)
	{
		bool bk=true;
		for(int i=1;i<=5;i++)if(map[5][i]==0){bk=false;break;}
		if(bk==false)return ;
		else ans=mymin(ans,step);
	}
	else
	{
		for(int i=1;i<=5;i++)
		{
			if(map[n-1][i]==0)
			{
				gai(n,i);step++;
			}
		}
		dfs(n+1,step);
	}
}
int main()
{
	int t=read();
	while(t--)
	{
		memset(map,0,sizeof(map));
		for(int i=1;i<=5;i++)
		{
			char ss[10];scanf("%s",ss+1);
			for(int j=1;j<=5;j++)
				mapc[i][j]=map[i][j]=ss[j]-'0';
		}
		ans=7;
		for(int i=0;i<1<<5;i++)
		{
			
			int step=change(i);
			dfs(2,step);
			memcpy(map,mapc,sizeof(mapc));
		}
		if(ans==7)printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}
/*
1
11101
11101
11110
11111
11111
*/