费解的开关

刘喆，陈新茹大约 4 分钟教学文档递推

费解的开关

题目描述

你玩过“拉灯”游戏吗？

$25$ 盏灯排成一个 $5 \times 5$ 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

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

下面这种状态

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

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

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

输入格式

第一行输入正整数 $n$ ，代表数据中共有 $n$ 个待解决的游戏初始状态。

以下若干行数据分为 $n$ 组，每组数据有 $5$ 行，每行 $5$ 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 $n$ 行数据，每行有一个小于等于 $6$ 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 $6$ 步以内无法使所有灯变亮，则输出 -1。

样例 #1

样例输入 #1

样例输出 #1

3
2
-1

提示

测试数据满足 $0 < n \le 500$ 。

题解

这题考察了递推。~~一开始以为是搜索，但是发现不太好写（~~，于是就考虑了其他的方法。可以看出，对于每行的灯泡，如果想把它打开，一定是要打开它自己的或者是他周围的灯。我们可以从上面往下一行一行的看，对于一个灭了的灯，我们如果改变他上面或者同一行的灯，就会影响我们之前处理好的结果，所以我们只需要去更改它下面的灯就行。

即，如果f[x][y]为关闭状态，我们只需要更改f[x][y+1]的值。

那么问题又来了，现在每一行的状态都由上一行得出，那么第一行的状态该如何确定？这里我直接枚举了第一行的每一种开关灯情况，一共32种情况，情况数不多，~~这里我直接打的表（~~

string map[6][10] = {
    {"00000"},
    {"10000", "01000", "00100","00010", "00001"},
    {"11000", "10100", "01100","10010", "01010", "00110","10001", "00101", "01001","00011"},
    {"11100", "11010", "10110","01110", "11001", "10101","01101", "10011", "01011","00111"},
    {"11110", "11101", "11011","10111", "01111"},
    {"11111"}
};

后来看其他大佬的代码，这里枚举可以用二进制运算来实现，上面的表从00000到11111对应了十进制的0~31，只要把十进制转换为二进制然后逐位判断即可。

网上大佬的部分代码

 for (int op = 0; op < 32; op ++ )
    for (int i = 0; i < 5; i ++ )
        if (op >> i & 1)
        {
            // code here
        }

代码

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

bool a[30][30] = {0}, b[30][30] = {0};
int map_size[6] = {1, 5, 10, 10, 5, 1};
// 暴力打表
string map[6][10] = {{"00000"},
                     {"10000", "01000", "00100", "00010", "00001"},
                     {"11000", "10100", "01100", "10010", "01010", "00110", "10001", "00101", "01001", "00011"},
                     {"11100", "11010", "10110", "01110", "11001", "10101", "01101", "10011", "01011", "00111"},
                     {"11110", "11101", "11011", "10111", "01111"},
                     {"11111"}};
int n;

void change(int x, int y) // 改变灯的状态
{
    b[x][y] = !b[x][y];
    b[x + 1][y] = !b[x + 1][y];
    b[x - 1][y] = !b[x - 1][y];
    b[x][y + 1] = !b[x][y + 1];
    b[x][y - 1] = !b[x][y - 1];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    while (n-- > 0)
    {
        for (register int i = 1; i <= 5; i++)
        {
            string line;
            cin >> line;
            for (register int j = 0; j < 5; j++)
                a[j + 1][i] = line[j] - '0';
        }

        int ans = 1000, cnt;
        for (register int i = 0; i < 6; i++) // 打表遍历第一行的情况
        {
            for (register int j = 0; j < map_size[i]; j++)
            {
                cnt = i;
                for (register int y = 1; y <= 5; y++)
                    for (register int x = 1; x <= 5; x++)
                        b[x][y] = a[x][y];  //  把矩阵存个副本
                for (register int x = 0; x < 5; x++)
                    if (map[i][j][x] == '1')   // 枚举第一行的情况
                        change(x + 1, 1);

                for (register int y = 1; y < 5; y++)
                    for (register int x = 1; x <= 5; x++)
                        if (!b[x][y])
                        {
                            change(x, y + 1);
                            cnt++;
                        }

                for (register int x = 1; x <= 5; x++)
                    if (!b[x][5])   // 最后一行如果出现了0，则无解
                    {
                        cnt = 1000;
                        break;
                    }
                ans = min(cnt, ans);
            }
        }
        cout << (ans > 6 ? -1 : ans) << endl;
    }
    return 0;
}