95. 费解的开关

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char g[10][10];
int n,t;
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
void turn(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx>=0&&xx<5&&yy>=0&&yy<5)
            g[xx][yy]^=1;
    }
}
void print()
{
    for(int i=0;i<5;i++)
        cout << g[i]<<endl;
}
int work()
{
    int ans=0x3f3f3f3f;
    for(int k=0;k<(1<<5);k++)
    {
        char buf[10][10];
        memcpy(buf,g,sizeof(g));
        int res=0;
        for(int i=0;i<5;i++)
        {
            if((k>>i)&1)
            {
                res++;
                turn(0,i);
                // print();
                // cout<<endl;
            }
        }
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<5;j++)
            {
                if(g[i][j]=='0')
                {
                    res++;
                    turn(i+1,j);
                    // print();
                    // cout<<endl;
                }
            }
        }
        bool ok=1;
        for(int i=0;i<5;i++)
        {
            if(g[4][i]=='0')
            {
                ok=0;
                break;
            }
        }
        //cout<<res<<" 01 "<<ok<<endl;
        //print();
        if(ok)
            ans=min(ans,res);
        memcpy(g,buf,sizeof(g));
    }
    //cout << ans<<" "<<res<<endl;
    if(ans>6)
        return -1;
    else
        return ans;
}
int main()
{
    cin >> t;
    while(t--)
    {
        for(int i=0;i<5;i++)
            cin>>g[i];
        // print();
        // cout<<endl;
        cout << work()<<endl;
    }
    return 0;
}

Donate