描述 Description
你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式 Input Format
第一行有一个正整数n，代表数据中共有n个待解决的游戏初始状态。
以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
对于30%的数据，n<=5；
对于100%的数据，n<=500。
输出格式 Output Format
输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若6步以内无法使所有灯变亮，请输出“-1”。
样例输入 Sample Input
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
样例输出 Sample Output
3
2
-1
分析：
枚举第一行再搜索其它的行。(方法有很多，只是我学d是这样做的)
算法：对于每个状态，算法只需要枚举第一行改变哪些灯的状态，只要第一行的状态固定了，接下来的状态改变方法都是唯一的：每一行需要改变状态的位置都在上一行中不亮的灯的正下面，因为只有这样才能使上一行的灯全亮。我们枚举第一行的状态改变方法（共2^5种），对于每种方法都依次改变下面几行的状态使上面一行灯全亮。到最后一行我们需要判断是否最后一行也恰好全亮，并更新最小步数.
【参考程序】：
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<iostream>
using namespace std;
typedef int array[6];
array a,b[6],c[6];
int n,ans;
void Init()
{
char str[6];
for (int i=1;i<=5;i++)
{
scanf("%s",str);
for (int j=1;j<=5;j++)
b[i][j]=str[j-1]-'0';
}
}
int work()
{
int dep=0;
for (int i=1;i<=5;i++)
if (a[i]==1)
{
dep++;
c[1][i]^=1; c[2][i]^=1;
if (i>1) c[1][i-1]^=1;
if (i<5) c[1][i+1]^=1;
}
for (int i=2;i<=5;i++)
for (int j=1;j<=5;j++)
if (c[i-1][j]==0 && dep<=6)
{
dep++;
c[i][j]^=1; c[i-1][j]^=1;
if (j>1) c[i][j-1]^=1;
if (j<5) c[i][j+1]^=1;
if (i<5) c[i+1][j]^=1;
}
if (dep>=7) return 7;
for (int i=1;i<=5;i++)
if (c[5][i]==0) return 7;
return dep;
}
void solve()
{
Init();
ans=0xFFFFFFF;
for (int a1=0;a1<=1;a1++)
for (int a2=0;a2<=1;a2++)
for (int a3=0;a3<=1;a3++)
for (int a4=0;a4<=1;a4++)
for (int a5=0;a5<=1;a5++)
{
memcpy(c,b,sizeof(c));
a[1]=a1; a[2]=a2; a[3]=a3; a[4]=a4; a[5]=a5;
int step=work();
if (step<ans) ans=step;
if (ans==2)
{
for (int i=1;i<=5;i++) printf("%d ",a[i]);
return ;
}
}
if (ans<=6) printf("%d\n",ans);
else printf("-1\n");
}
int main()
{
scanf("%d",&n);
for (int test=1;test<=n;test++) solve();
return 0;
}