费解的开关

题目

你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式
第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。
以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
输出格式
一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。
数据范围
0<n≤500

输入样例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例：
3
2
-1

分析

题意为给出一个5*5的矩阵，0代表灯是关着的，1代表灯是开着的，问能不能在6步之内把所有的灯都变成全开着的，变化规则是如果一个灯按了一次之后，这个灯的状态就会改变，并且它的上下左右的灯的状态都会改变
首先，每个灯只能按一次，因为按了两次之后等于没有操作，
如果对第一行的灯操作完了之后，操作第二行的灯时，如果第一行的灯有灭的话，那么第二行这个位置的灯就要按一下，因为第一行的灯不能操作之后就只有第二行的灯能让他的状态改变，同样，第二行操作完了之后开始第三行的，如果第二行有的灯灭的话那么第三行这个位置的灯就要按一下，同样第四行，然后第五行的话，因为已经没有下一行为第五行灭了的灯点亮了，所以，第五行要判断一下是不是全亮的

可以先枚举一下第一行的所有状态，第一行的所有状态有2的5次方种状态，可以用0-31可以表示这些状态，0-31每一个数都有一个二进制数与之对应，0可表示为00000，1表示为00001，如果二进制的某一位为1则表示这个位置的灯要进行一次操作，然后依次遍历第1-4行，最后判断第五行是不是全亮的

代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
int n; char ch[12][12],c[12][12];
int dir[5][2]={0,0,-1,0,0,-1,1,0,0,1};

int check()
{//判断第五行是不是全亮的
    for(int i=0;i<5;i++)
    {
        if(ch[4][i]=='0') return 0;
    }
    return 1;
}

void work(int x,int y)
{//对某一位置和上下左右进行状态变化
    for(int i=0;i<5;i++)
    {
        int xx=x+dir[i][0];int yy=y+dir[i][1];
        if(xx<0||xx>=5||yy<0||yy>=5) continue;
        ch[xx][yy]=ch[xx][yy]^1;
    }//‘0’为48，‘1’为49，直接异或就可以
}
int main()
{
    cin>>n;
    while(n--)
    {
        int ans=123456789;
        for(int i=0;i<5;i++) cin>>ch[i];

        for(int op=0;op<32;op++)
        {//枚举第一行的状态
            int step=0;
            memcpy(c,ch,sizeof ch);
            for(int i=0;i<5;i++)
            {
                if(op>>i & 1)
                {//如果二进制数op中这一位为1就对这个位置进行操作
                    step++;
                    work(0,i);
                }
            }

            for(int i=0;i<4;i++)
            {
                for(int j=0;j<5;j++)
                {//依次遍历第0，1，2，3行，如果这个位置的灯是灭的就按一下下一行的这个位置的灯
                    if(ch[i][j]=='0')
                    {
                        step++;
                        work(i+1,j);
                    }
                }
            }

            if(check()) ans=min(ans,step);
            memcpy(ch,c,sizeof(ch));//每一次操作都是在输入给出的矩阵下操作的，
                                    //所以每一次都要进行一下备份
        }

        if(ans<=6) cout<<ans<<endl;
        else cout<<-1<<endl;
    }
}