题目描述

25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。

C++ 代码

#include<bits/stdc++.h>

using namespace std;
const int N = 6;
char g[N][N],bg[N][N];
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};

void turn(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        int a = x + dx[i],b = y + dy[i];
        if(a<0||a>4||b<0||b>4)continue;
        g[a][b]^=1;
    }
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        for(int i=0;i<5;i++)scanf("%s",&bg[i]);
        int res = 10;
        //这里我们枚举第一行的32种按法，不管是灭还是亮，把第一行情况全都遍历一遍
        //这个时候保证第0行的灯全都是亮的状态，这个时候按照上述方法，再次遍历第二行，
        //从而保证第一行的灯全都是亮的状态。
        //当遍历到最后一行时，这时候除了最后一行全都是亮的状态，就表示无解。
        for(int op=0;op<32;op++)//每行32种操作
        {
            int cnt = 0;//总共按了几次
            memcpy(g,bg,sizeof g);
            for(int i=0;i<5;i++)//对第1行5个灯进行操作
            {
                if(op>>i&1)//op为1表示按一下，0表示不按
                {
                    turn(0,i);//对第i个灯按一下
                    cnt++;//次数加一
                }
            }
            //通过第一行判断第2~4行按不按
            for(int i=0;i<4;i++)
            {
                for(int j=0;j<5;j++)
                {
                    if(g[i][j]=='0')
                    {
                        turn(i+1,j);
                        cnt++;
                    }

                }
            }
            bool flag = true;
            //检查最后一行是不是全亮
            for(int i=0;i<5;i++)
                if(g[4][i]=='0')
                    flag = false;
            if(flag&&res>cnt)res = cnt;

        }
        if(res>6)printf("-1\n");
            else printf("%d\n",res);
    }
    return 0;
}