- 使用dfs完成
#include<bits/stdc++.h>
using namespace std;
const int N = 6;
char g[N][N],backup[N][N];
int dx[5]={-1,0,1,0,0};
int dy[5]={0,1,0,-1,0};
int st[N];
int res=10;
void turn(int x,int y)
{
for(int i=0;i<5;i++)
{
int a = dx[i] + x;
int b = dy[i] + y;
if(a<0||a>=5||b<0||b>=5) continue; //出界
if(g[a][b]=='0') g[a][b]='1';
else g[a][b]='0';
//也可以直接使用
//g[a][b] ^=1;
//'0'的ASCII是48 110000
//'1'的ASCII是49 110001
//只有最后一位不同 直接异或
}
}
void dfs(int u) //当前选的位置
{
//1表示选 2表示不选
if(u==5)
{
int step = 0;
memcpy(backup,g,sizeof g); //备份
//5个位置
for(int i=0;i<5;i++)
{
if(st[i]==2)//不选 当前位置是0
{
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;
break;
}
}
if(!dark) res = min(res,step);
memcpy(g,backup,sizeof backup);
return ;
}
st[u]=2;
dfs(u+1);
st[u]=0;
st[u]=1;
dfs(u+1);
st[u]=0;
}
int main()
{
int T;
cin>>T;
while(T--)
{
for(int i=0;i<5;i++) cin>>g[i];
dfs(0);
if(res>6) res=-1;
cout << res <<endl;
res=10;
}
return 0;
}
```