95. 费解的开关【二级制枚举】

二进制枚举第一行的操作状态。

#include<bits/stdc++.h>
using namespace std;
const int N=30;
char a[N][N],b[N][N];
int n,ans;
int dx[5]={0,-1,0,0,1};
int dy[5]={0,0,-1,1,0};
char get(char c)
{
    if(c=='0') return '1';
    else return '0';
}
void solve(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        int tempx=x+dx[i],tempy=y+dy[i];
        if(tempx>=0&&tempx<5&&tempy>=0&&tempy<5) 
            a[tempx][tempy]=get(a[tempx][tempy]);
    }
}
void dfs(int x)
{
    memcpy(a,b,sizeof b);
    int cnt=0,flag=1;
    for(int i=0;i<5;i++) if((x>>i)&1) solve(0,i),cnt++;
    for(int i=1;i<5;i++)
        for(int j=0;j<5;j++) if(a[i-1][j]=='0') solve(i,j),cnt++;
    for(int i=0;i<5;i++) if(a[4][i]=='0') flag=0;
    if(flag) ans=min(ans,cnt);
}
int main(void)
{
    cin>>n;
    while(n--)
    {
        for(int i=0;i<5;i++)
            for(int j=0;j<5;j++) 
                cin>>a[i][j],b[i][j]=a[i][j];
        ans=7;
        for(int i=0;i<(1<<5);i++) dfs(i);
        printf("%d\n",ans>6?-1:ans);
    }
    return 0;
}