用二进制枚举第一行的状态,通过第一行的状态更新之后的整个矩阵的状态
#include<bits/stdc++.h>
using namespace std;
int dx[10]={1,-1,0,0};
int dy[10]={0,0,1,-1};//向上,向下,向右,向左
const int inf=1000000;
int n;
int a[10][10];
string s;
int ans;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void changed (int x,int y)
{
a[x][y]^=1;
for(int i=0;i<4;++i)//对于方向数组只有4个数字,所以就只是[0,4)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<0||yy<0) continue;
a[xx][yy]^=1;
}
}
bool check()
{
for(int j=0;j<5;++j)
if(!a[4][j])
return false;
return true;
}
void dfs(int layer,int tot)
{
if(tot>6) return ;
if(layer==5&&check())
{
ans=min(ans,tot);
return ;
}
int re=0;//re是用来恢复被修改过后的点
for(int i=0;i<5;++i)
if(!a[layer-1][i])//用上一行的点的状况更新当前点的状况
re|=1<<i,changed(layer,i),tot++;
dfs(layer+1,tot);
for(int i=0;i<5;++i)
if(re&(1<<i))
changed(layer,i);
}
int main()
{
n=read();
while(n--)
{
ans=inf;
//输入
for(int i=0;i<5;++i)
{
cin>>s;
for(int j=0;j<5;++j)
a[i][j]=s[j]-'0';
}
for(int i=0;i<(1<<5);++i)//二进制枚举每一行的状态
{
int tot=0;
int s=i;
for(int j=0;j<5;++j)
if(s&(1<<j))
changed(0,j),tot++;//改变第一行的状态
dfs(1,tot);
for(int j=0;j<5;++j)//复原你原来的01矩阵的状态
if(s&(1<<j))
changed(0,j);
}
//判断是否又被更新
if(ans==inf) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}