费解的开关

问题

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

输入样例

输出样例

3
2
-1

思路

递推，枚举所有状态搜索

没什么刷题经验，一开始看这道题比较懵。若毫无章法的瞎按灯，前面按亮的灯，可能在后序的操作中，使其再次被按灭。所以需要一个按灯方案，使得后序操作不影响前面已经按亮的灯。

枚举第1行的所有操作，共2^5种按灯方案。使得第一行的状态确定，再由第一行依次递推出后面的操作。最后判断方案可行。

只通过下一行去打开上一行的灯。这样我们可以由第i行的状态，可确定递推出下一行，即i+1行的操作。需要注意的是，最后一行的状态，由上一行确定。在最后查看第五行的状态，即可确定该方案是否可行。

如何进行枚举：if (k >> j & 1) //第j位是否为1，1表示该位置需要按下操作。
备份操作：开始之前将初始状态进行备份，以便枚举下一方案。

代码

知识积累

二进制进行状态压缩：k >> j & 1, 字符，int 0/1可直接异或
二维数组的定义，必须确定列数：dx[][4]
利用一维数组，进行前后左右4个方向的遍历：dx[] = {0, -1, 0, 1, 0}, nx = x + dx[i]
数组的拷贝：memcpy(backup, light, sizeof(light));

调试过程

从源头出发，对每一阶段进行黑盒测试。判断是否符合预期。

1. 字符0的比较
2. 备份时机不对
3. 灯的初始状态赋值

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

int INF = 100000;
char light[6][6]; //使用char更省空间,数组最好开大点
void turn(int x, int y)
{
    int dx[] = {0, -1, 0, 1, 0}, dy[] = {0, 0, 1, 0, -1}; 
    for (int i = 0; i < 5; i++) //5个方向都需变动，方向的操作不熟
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) light[nx][ny] ^= 1; //边界的判断，字符，int 0/1可直接异或
    }
}

int work() //由上一行，递推确定下一行的操作
{
    int ans = INF;
    for (int k = 0; k < (1 << 5); k++) //枚举第一行的情况，如何枚举2^5种按灯方案
    {
        int res = 0;
        char backup[6][6];
        memcpy(backup, light, sizeof(light)); //开始之前将初始状态进行备份，以便枚举下一方案
        for (int j = 0; j < 5; j++) //按下第0行
        {
            if (k >> j & 1) //第j位是否为1，1表示该位置需要按下操作
            {
                res++;
                turn(0, j);
            }
        }
        for (int i = 0; i < 4; i++) //第1行到第4行，第5行由第4行确定，故不能再操作
        {
            for (int j = 0; j < 5; j++)
            {
                if (light[i][j] == '0')
                {
                    res++;
                    turn(i+1, j);
                }
            }
        }
        bool suc = false;
        //判断第5行是否全为1，否者此方案不可行
        for (int i = 0; i < 5; i++)
        {
            if (light[4][i] == '0') //与字符0做比较，容易写成int 0
            {
                suc = false;
                break;
            }
            else suc = true;
        }
        memcpy(light, backup, sizeof(backup)); //判断方案可行后，才将light恢复备份
        if (suc)
            ans = min(ans, res); //若方案失败，则不参与比较
    }
    return ans <= 6 ? ans : -1;
}

int main()
{
    int n; cin >> n;
    while (n--)
    {
        for (int i = 0; i < 5; i++)
        {
            char on;
            for (int j = 0; j < 5; j++)
            {
                cin >> on;
                light[i][j] = on;
            }
        }
        cout << work() << endl;
    }
}