每日算法打卡：费解的开关 day 3

原题链接

95. 费解的开关

题目难度：中等

题目来源：《算法竞赛进阶指南》

题目描述

你玩过“拉灯”游戏吗？

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 个字符。

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

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

输出格式

一共输出 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的矩阵来表示灯的亮灭，用1来表示亮，用0来表示灭，每一次按开关会使这个灯和他上下左右的五盏灯全部改变状态，问是否能在6步之内将所有的灯全部按亮

这道题的难点在于如何确定一个方法，能够有条理有逻辑的将所有灯全部按亮

我们可以用一个类似于魔方的想法，一层一层恢复

例如

11011
01011
10001
11010
11100

我们想要使第一行第三个的数字变成1，那么就应该按第二行第三个位置的数据，这样第一行就可以完全变为1，同理，我们要把第二行的0变成1，则只需要按下对应第三行的开关即可，直到递推到将倒数第二行恢复完成，最后判断最后一行是否全为1，如果不是就说明这个情况无法全为1的

这里就引出来一个问题，我们如何确定这样的方式是结果最小的呢，换句话说，那么我们如何确定第一行的状态呢，因此就需要遍历第一行的状态，这里就需要用到之前我们讲的指数型枚举了，对应的就是2的5次方，是32种情况，这样就可以达到不重不漏的效果了

这里就引出了第二个问题，如何简易的实现0和1中5位的指数型枚举，从0到31，刚好对应二进制的5个位，因此从0遍历到31刚好可以分别对应5个位置的所有情况，并且我们将二进制的1代表这个位置将要按下开关，将0代表不按下开关，这样就能实现二进制的指数型枚举

示例代码

#include<iostream>
#include<memory.h>
using namespace std;
bool light[5][5];// 用于表示灯的亮灭

void turn(int x, int y) // 表示按一次开关
{
    light[x][y] = !light[x][y];
    if (x - 1 >= 0)
        light[x - 1][y] = !light[x - 1][y];
    if (y - 1 >= 0)
        light[x][y - 1] = !light[x][y - 1];
    if (x + 1 < 5)
        light[x + 1][y] = !light[x + 1][y];
    if (y + 1 < 5)
        light[x][y + 1] = !light[x][y + 1];
}

void func() // 用于计算结果的函数
{
    int ans = 9999; // 表示最小的按灯次数，初始化为较大的数方便更新
    for (int i = 0; i < 32; i++)
    {
        bool backup[5][5]; // 因为每次操作之后需要恢复，我们采用备份
        memcpy(backup, light, sizeof(light));
        int step = 0; // 记录本次操作的结果
        // 从0到31，刚好对应二进制的5个位，因此从0遍历到31刚好可以分别对应5个位置的所有情况，并且我们将二进制的1代表这个位置将要按下开关，将0代表不按下开关，这样就能实现二进制的指数型枚举
        for (int j = 0; j < 5; j++)
        {
            if ((i >> j & 1) == 1) // 判断最后一位是否为1
            {
                step++;
                turn(0, j);
            }
        }

        for (int i = 0; i < 4; i++) // 从第一行开始遍历位置，如果是灭的，则按下这个位置对应的下一面一个位置的开关
        {
            for (int j = 0; j < 5; j++)
            {
                if (light[i][j] == false)
                {
                    step++;
                    turn(i + 1, j);
                }
            }
        }
        
        bool dark = false;
        for (int i = 0; i < 5; i++) // 判断最后一行是否符合要求，如果不符合要求则需要将标记更改
        {
            if (light[4][i] == false)
            {
                dark = true;
                break;
            }

        }
        
        if (dark == false) // 如果符合要求，则取较小的数作为结果
            ans = min(ans, step);
        
        memcpy(light, backup, sizeof(backup)); // 恢复原状，进入下一种情况
    }
    if (ans > 6)
        ans = -1;
    cout << ans << '\n';
}
int main()
{
    int T;
    cin >> T; // 表示有T组数据
    while (T--)
    {
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++) // 读取数据
            {
                char in;
                cin >> in;
                if (in == '1')
                    light[i][j] = true;
                else
                    light[i][j] = false;
            }
        }
        func();
    }
    return 0;
}