题目描述
本题为递推的好题
思路
思路和书中所写差不多,代码也是按照书的思路写的,先确定第一行,然后推出第2,3,4,5行
C++ 代码
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
int t;
string a[6];
string arr[6];
int dx[]={1,0,-1,0,0};
int dy[]={0,1,0,-1,0};
int res=0;
bool winn;
int jie;
void change(int x,int y)
{
for(int i=0;i<5;i++)
{
int a1=x+dx[i],b1=y+dy[i];
if(a1<0 || a1>=5 || b1<0 || b1>=5) continue;
if(a[a1][b1]=='1') a[a1][b1]='0';
else if(a[a1][b1]=='0') a[a1][b1]='1';
}
}
void dfs(int line)
{
if(res>6) return;
if(line==5) return;
for(int i=0;i<5;i++)
{
if(a[line-1][i]=='0')
{
change(line,i);
res++;
}
}
dfs(line+1);
}
void solve()
{
jie=0x3f3f3f3f;
for(int i=0;i<5;i++)
cin>>arr[i];
for(int i=0;i<(1<<5);i++)
{
for(int j=0;j<5;j++)
a[j]=arr[j];
res=0;
winn=false;
for(int j=0;j<5;j++)
if((i>>j)&1) change(0,j),res++;
dfs(1);
for(int j=0;j<5;j++)
if(a[4][j]=='0') winn=true;
if(winn==false&&res<=6) jie=min(jie,res);
}
if(jie>0x3f3f3f3f/2) printf("-1\n");
else printf("%d\n",jie);
}
int main()
{
scanf("%d",&t);
while(t--) solve();
return 0;
}