AcWing 95. 费解的开关
原题链接
中等
作者:
Lyle2021
,
2021-01-19 10:32:48
,
所有人可见
,
阅读 218
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
char g[10][10];
int dx[]={0,-1,0,1,0},dy[]={0,0,1,0,-1};
void turn(int x,int y){
for(int i=0;i<5;i++){
int a=x+dx[i],b=y+dy[i];
g[a][b]^=1;
}
}
int work(){
int ans=1000000;
char b[10][10];
memcpy(b,g,sizeof g);
for(int k=0;k<1<<5;k++){
int res=0;
for(int j=0;j<5;j++){
if(k>>j&1){//32种枚举
res++;
turn(0,j);
}
}
for(int i=0;i<4;i++){
for(int j=0;j<5;j++){
if(g[i][j]=='0'){
res++;
turn(i+1,j);
}
}
}
for(int j=0;j<5;j++){
if(g[4][j]=='0'){
res=-1;
break;
}
}
if(res==-1){
memcpy(g,b,sizeof b);
continue;
}else{
ans=min(ans,res);
memcpy(g,b,sizeof b);
}
}
if(ans<=6)return ans;
else return -1;
}
int main(){
int n;
cin>>n;
while(n--){
for(int i=0;i<5;i++){
cin>>g[i];
}
cout<<work()<<endl;
}
return 0;
}