95. 费解的开关

题目链接：活动 - AcWing

思路：先学习黑白迭代游戏玩法，先枚举按第一行的所有情况，然后当上一行有没有点亮的灯时，一定要按这个灯正下方的灯；反之，如果这行的某个灯正上方的灯已经点亮，那么一定不能按这个灯，否则上面的灯就会熄灭，且在以后的操作中无法再次被点亮。

因此枚举第一行turn的所有情况，然后模拟后四行，判断最终有没有将所有灯都点亮，若点亮，则判断是否需要更新最小次数；否则，继续。

代码：

#include<iostream>
#include<cstring>
using namespace std;

int T;
char ch[7][7],map[7][7];
int dir[5][2]={0,1,0,-1,1,0,-1,0,0,0};
int cnt,ans;

void turn(int x,int y)
{
    for(int i=0;i<5;++i)
    {
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(ch[xx][yy]=='0') ch[xx][yy]='1';
        else ch[xx][yy]='0';
    }
}

bool check()
{
    for(int i=1;i<=5;++i)
    {
        for(int j=1;j<=5;++j)
        {
            if(ch[i][j]=='0') return false;
        }
    }
    return true;
}

void work()
{
    for(int i=0;i< 1<<5 ;i++ )
    {
        memcpy(ch,map,sizeof map);
        cnt=0;
        for(int j=0;j<5;j++)
        {
            if(i >> j & 1 ) turn(1,j+1),cnt++;
        }
        
        for(int x=2;x<=5;++x)
        {
            for(int y=1;y<=5;++y)
            {
                if(ch[x-1][y]=='0') turn(x,y),cnt++;
            }
        }
        
        if(check()) ans=min(ans,cnt);
    }
}

int main()
{
    cin>>T;
    while(T--)
    {
        ans=7;
        for(int i=1;i<=5;i++) cin>>map[i]+1;
        
        work();
        
        if(ans==7) puts("-1");
        else cout<<ans<<endl;
    }
    
    return 0;
}