我们容易发现,如果某一行灯的状态确定时,只有其下一行能改变,而为了达到所有灯都亮,其下一行必须按照点亮上一行所有灯光的策略进行,往下同理
由此可见,当第一行的状态确定时,第二行,第三行直到最后的状态都是确定的
从而枚举第一行的所有操作,共31种,用二进制表示为0~2^5-1
往后每一行都按照点亮上一行未亮的灯的策略进行,到最后判断最后一行是否全亮
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 6;
int dx[N] = {-1, 0, 1, 0}, dy[N] = {0, 1, 0, -1};
char g[N][N], backup[N][N];
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;
// '0' 48 110000
// '1' 49 110001
// ^=1 改变最后一位,0变1 1变0
//替换成if判断也行,无所谓
}
}
int main()
{
int t;cin>>t;
while(t--)
{
for(int i=0;i<5;i++) cin>>g[i];
int res=0x3f3f3f3f;
//第一行有0~2^5-1种操作
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 flag=false;//最有一行若有灯未亮,则失败
for(int j=0;j<5;j++)
if(g[4][j]=='0')
flag=true;
if(!flag) res=min(res,step);
memcpy(g,backup,sizeof g);//恢复初始状态
}
if(res>6) cout<<-1<<endl;
else cout<<res<<endl;
}
}