题目描述
游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“1”表示一盏开着的灯,用数字“0”表示关着的灯。下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成:
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成:
01111
11001
11001
10100
11011
给定一些游戏的初始状态,编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式
第一行输入正整数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
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6;
char g[N][N],backup[N][N];
int dx[]={-1,0,1,0,0},dy[]={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;
g[a][b]^=1;
}
return;
}
//递推二维
//规律:1.顺序可以任意
// 2.每个格子最多操作一次
//每一行的操作完全由上一行决定
//枚举第一行操作(可位运算也可递归;位运算:op>0&&op<32,op>>i&1(开关操作),op++)
//turn(x,y),(开关操作,上下左右+本身:开关操作)
int main(){
int t;
cin>>t;
while(t--){
for(int i=0;i<5; i++)cin>>g[i];
int res=10;
for(int op=0;op<32;op++){//位运算枚举第一行每个方案
memcpy(backup,g,sizeof g);
int step=0;
for(int i=0;i<5;i++)
if(op >> i & 1){
step++;
turn(0,i);
}
for(int i=0;i<4;i++)
for(int j=0;j<5;j++)
if(g[i][j]=='0'){
step++;
turn(i+1,j);
}
bool dark=false;
for(int i=0;i<5;i++){
if(g[4][i]=='0')dark=true;
}
if(!dark)res=min(res,step);
memcpy(g,backup,sizeof g);
}
if(res>6)res=-1;
cout<<res<<endl;
}
return 0;
}