题目描述

你玩过“拉灯”游戏吗？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

正解

大致解题思路：这道题目首先看一眼，我们就可以知道必然与位运算有着密切的关系，因为出现了0和1，这是一个重要的发现，接着我们在仔细分析题意，我们知道如果纯暴力枚举的话，必然是会超时的，那么如何优化呢？因此我们需要从题目中找出非常有用的性质来优化，这是一个大致的思路方向

1. 每一个位置顶多只会操作一次。因为如果操作两次的话，相当于不操作，必然是不满足最优解。

2. 在一套方案中，操作的顺序无关紧要，这一个略加思索便可得知

3. 最重要的性质，如果我们确定了第I行的操作方案的话，那么后面的行数都可以依此递推，下面给出一个详细的解答。

11011
10110
01111
11111
比如说这个例子，如果我们确定了第1行，那么第二行所有的0(坐标：a[i][j])
都只能是第三行a[i+1][j]来修改了，因为如果你第二行修改的话，那么第一行将会打乱，下面每一行依此类推。

所以说，我们只需要得出第一行的顺序，后面的顺序都可以顺序推出

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,k,a[7][7],ans1=1e6,b[7][7];//7,7是因为怕在最后一排溢出
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        getchar();
        for (i=1;i<=5;i++)
        {
            for (j=1;j<=5;j++)
            {
                char ch=getchar();
                b[i][j]=ch-'0';
            }
            getchar();
        }
        for (i=0;i<=(1<<5);i++)
        {
            for (j=1;j<=5;j++)
            {
                for (k=1;k<=5;k++)
                    a[j][k]=b[j][k];
            }
            int ans=0;
            for (j=1;j<=5;j++)
                if (i>>(j-1) & 1)
                {
                    ans++;
                    a[1][j-1]^=1;
                    a[1][j+1]^=1;
                    a[1][j]^=1;
                    a[2][j]^=1;
                }
            for (j=1;j<=4;j++)//切记是1~4，而不是2~5，因为我们是控制i+1行，而不是控制第i行
                for (k=5;k>=1;k--)
                    if (!a[j][k])
                    {
                        ans++;
                        a[j][k]^=1;//上面
                        a[j+2][k]^=1;//下面
                        a[j+1][k]^=1;//本身
                        a[j+1][k+1]^=1;//右面
                        a[j+1][k-1]^=1;//左面
                    }
            //cout<<ans<<endl;
            bool ok=true;
            for (j=1;j<=5;j++)
                for (k=1;k<=5;k++)
                    if (!a[j][k])
                        ok=false;
            if (ok)
                ans1=min(ans1,ans);//,cout<<ans<<endl;
        }
        if (ans1>6)
            cout<<-1;
        else
            cout<<ans1;
        ans1=1e7;
        puts("");
    }
    return 0;
}

解法二

运用模块化编程

#include <bits/stdc++.h>
using namespace std;
int a[7][7],b[7][7],n,answer;
int init()
{
    getchar();
    for (int i=1;i<=5;i++)
    {
        for (int j=1;j<=5;j++)
        {
            char ch=getchar();
            a[i][j]=ch-'0';
        }
        getchar();
    }
}
int handle(int x,int y)
{
    b[x][y]^=1;
    b[x-1][y]^=1;
    b[x][y+1]^=1;
    b[x][y-1]^=1;
    b[x+1][y]^=1;
}
bool judge(void)
{
    for (int i=1;i<=5;i++)
        for (int j=1;j<=5;j++)
            if(!b[i][j])
                return false;
    return true;
}
int work(void)
{
    answer=1e7;
    for (int i=1;i<=(1<<5);i++)
    {
        int ans=0;
        memcpy(b,a,sizeof(a));
        for (int j=1;j<=5;j++) 
            if (i>>(j-1) & 1)
            {
                handle(1,j);
                ans++;
            }
        for (int j=1;j<=4;j++)
            for (int k=1;k<=5;k++)
                if (!b[j][k])
                {
                    ans++;
                    handle(j+1,k);
                }
        if (judge())
            answer=min(ans,answer);
    }
    return answer;
}
int main()
{
    cin>>n;
    while(n--)
    {
        init();
        if (work()<=6)
            cout<<answer;
        else
            cout<<"-1";
        puts("");    
    }
    return 0;
}