费解的开关
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
你玩过“拉灯”游戏吗？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个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。 对于30%的数据，n≤5n \leq 5n≤5； 对于100%的数据，n≤500n \leq 500n≤500。
输出描述:
输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。 对于某一个游戏初始状态，若6步以内无法使所有灯变亮，请输出“-1”。
示例1
输入
复制3 00111 01011 10001 11010 11100 11101 11101 11110 11111 11111 01111 11111 11111 11111 11111
3 00111 01011 10001 11010 11100 11101 11101 11110 11111 11111 01111 11111 11111 11111 11111
输出
复制3 2 -1
3 2 -1
思路：
状压确定第一行的改法，来实现后面的改法
代码：
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9+10;
int t;
char g[10][10];
int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
//由于发现确定一行的灯状态，下一行也就确定了，因为改下一行会修改上一行，所以下一行就被确定了
void turn(int x,int y){//改状态
for(int i=0;i<5;++i){
int a=dx[i]+x,b=dy[i]+y;
if(a>=0&&a<5&&b>=0&&b<5)g[a][b]^=1;
}
}
int work(){
int res=INF;//最小次数
for(int i=0;i<1<<5;++i){//枚举所有改第一行的灯的选法
char f[10][10];//容器
int step=0;//当前选法需要次数
memcpy(f,g,sizeof g);//存于原始数据
for(int j=0;j<5;++j){
if(i>>j&1){//改
turn(0,j);
step++;
}
}
for(int i=0;i<4;++i){//发现前0~3行有0，有他的i+1行来改变
for(int j=0;j<5;++j){
if(g[i][j]=='0'){turn(i+1,j);step++;}
}
}
bool flag=1;
for(int i=0;i<5;++i)if(g[4][i]=='0'){flag=0;break;}//如果最后一行无0，说明此次选法有用
if(flag==1){
res=min(res,step);//判断最小
}
memcpy(g,f,sizeof g);
}
if(res<=6)return res;
else return -1;
}
int main(){
cin.tie(0);
cin>>t;
while(t--){
for(int i=0;i<5;++i){
for(int j=0;j<5;++j){
cin>>g[i][j];
}
}
cout<<work()<<endl;
}
}