拉灯游戏

题面描述

你玩过“拉灯”游戏吗？25盏灯排成一个5×5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 　　我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

10111

01101

10111

10000

11011

　　在改变了最左上角的灯的状态后将变成：

01111

11101

10111

10000

11011

　　再改变它正中间的灯后状态将变成：

01111

11001

11001

10100

11011

　　给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式

第一行有一个正整数n，代表数据中共有n个待解决的游戏初始状态。 　　以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。 　　对于30%的数据，n<=5； 　　对于100%的数据，n<=500。

输出格式

输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。 　　对于某一个游戏初始状态，若6步以内无法使所有灯变亮，请输出“-1”。

样例

我们从题目当中可以分析出来，我们现在要把所有灯都打开，并且要最少的次数，所以可以从这个里面的出每个按钮至多按一次，因为按两次相当于没有按，所以我们就可以得出第一行一共有32种状态2^5。所以，我们可以直接枚举所有的状态，然后找到方案数最少的，我们可以先把第一行全部打开，然后锁死，i只能由i+1来变化，到最后一行停止，然后判断一下最后一行是不是全开，如果全开证明合法，然后方案数取min即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int dx[5]={0,0,0,+1,-1};
const int dy[5]={+1,-1,0,0,0};
char g[10][10];
void turn(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=0&&xx<5&&yy>=0&&yy<5)
        {
            g[xx][yy] = '0' + !(g[xx][yy] - '0');
        }
    }
}
int work()
{
    char jk[10][10];
    int minn=1000000;
    for(int i=0;i<1<<5;i++)
    {
        int res=0;
        memcpy(jk,g,sizeof(g));
        for(int j=0;j<5;j++)
        {
            if(i>>j&1)
            {
                res++;
                turn(0,j);
            }
        }
        for(int j=0;j<4;j++)
        {
            for(int k=0;k<5;k++)
            {
                if(g[j][k]=='0')
                {
                    res++;
                    turn(j+1,k);
                }
            }
        }
        bool p=1;
        for(int j=0;j<5;j++)
        {
            if(g[4][j]=='0')
            {
                p=0;
                break;
            }
        }
        if(p)
        {
            minn=min(minn,res);
        }
        memcpy(g,jk,sizeof(jk));
    }
    if(minn>6)
    return -1;
    return minn;
}
int main()
{
	freopen("input.in","r",stdin);
	freopen("output.out","w",stdout);
    int t;
    cin>>t;
    while(t--)
    {
        for(int i=0;i<5;i++)
        {
            cin>>g[i];
        }
        cout<<work()<<endl;
    }
}