关于算法:递推算法题令人费解的开关『拉灯』

32次阅读

共计 2233 个字符，预计需要花费 6 分钟才能阅读完成。

题目起源 AcWing。

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

<p> 每一个灯都有一个开关，游戏者能够扭转它的状态。</p>

每一步，游戏者能够扭转某一个灯的状态。

<p> 游戏者扭转一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地扭转其状态。</p>

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

<p> 上面这种状态 </p>

<p> 在扭转了最左上角的灯的状态后将变成：</p>

<p> 再扭转它正中间的灯后状态将变成：</p>

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

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

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

<p> 每组数据形容了一个游戏的初始状态。</p>

<p> 各组数据间用一个空行分隔。</p>

一共输入 $n$ 行数据，每行有一个小于等于 $6$ 的整数，它示意对于输出数据中对应的游戏状态起码须要几步能力使所有灯变亮。

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

$0 \le n \le 500$

3
2
-1

首先有三点很重要的性质须要阐明：

如果按哪些灯确定了，那么按这些灯的程序不重要，无论什么程序，后果都是雷同的
咱们没有必要按一盏灯两次及以上，因为，按两次，相当于没按，按三次，相当于按两次 + 一次（也就是一次）

因而：

因为按灯的程序不重要，咱们能够先把第一行的灯都按了
咱们发现，第一行想按的灯都按过之后，如果想要让第一行全亮，那么我第二行只能有一种按法，就是按第一行不亮的灯的上面的灯（上面是例子）

 第一行状态 10011（1 代表亮的灯）第二口头作 01100（1 代表按按钮）

那么，咱们怎么保障第二行全亮呢？只能用第三行来解决！

那么，咱们怎么保障最初一行（第五行）全亮呢？没法保障！

咱们发现，如果第一行按法确定了，那么接下来二三四五行的按法和能不能全亮就确定了。

因而，对于任意一种输出状态，咱们把第一行 32 种按法全副遍历一遍，看看哪些能够全亮（通过检测第五行状态），这些全亮的种有没有操作次数小于等于 6 的。有的话，就返回这个操作数，否则就返回 -1 呗。

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

const int N = 5 + 5;   // 加上 5 更保险
// 留神接管时用字符串更不便，因为输出流每行没有空格
char g[N][N];  // 记录灯目前的状况

// 上右下左中
int dx[5] = {0, 1, 0, -1, 0};
int dy[5] = {1, 0, -1, 0, 0};

// 按第 x 行第 y 列，自身和上下左右五个灯都取反
void turn(int x, int y)
{for (int i = 0; i < 5; ++ i)
    {int a = x + dx[i], b = y + dy[i];
        if (0 <= a && a < 5 && 0 <= b && b < 5)
            g[a][b] = g[a][b] == '1' ? '0': '1';
    }
}

int work()
{
    int ans = 2e9;
    // 第一层循环，把所有第一行按的状况都遍历
    // k 是被压缩了的状态，最小 0b00000 代表都不按，// 最大 0b11111 代表都按
    
    // 备份，因为上面的操作会扭转 g
    char backup[N][N];
    memcpy(backup, g, sizeof g);

    for (int k = 0; k < (1 << 5); ++ k)
    {
        // 确保咱们的 g 是输出的 g
        memcpy(g, backup, sizeof backup);

        // 当第一行为 k 时，总操作次数是..
        int res = 0;  // 用 res 来记录

        // 执行 k（依据 k 把第一行按了）for (int j = 0; j < 5; ++ j)
        {if (k >> j & 1)
            {
                res ++;
                turn(0, j);
            }
        }
        
        // 第一行确定了，第二行就确定了
        // 因为只有正当操作第二行
        // 能力把第一行全副点亮
        // 以此类推，第二行定了后，第三行就被第二行决定了
        for (int i = 0; i < 4; ++ i)
        {for (int j = 0; j < 5; ++ j)
            {if (g[i][j] == '0')
                {
                    res ++;
                    turn(i + 1, j);
                }
            }
        }

        // 下面的操作肯定能保障前 4 行全亮
        // 然而第 5 行不肯定全亮，第 5 行全亮，才是真正无效的操作
        bool success = true;
        for (int j = 0; j < 5; ++ j)
        {if (g[4][j] == '0')
            {
                success = false;
                break;
            }
        }
        
        // 如果是无效的操作，咱看看一共按了几次开关
        if (success) ans = min(res, ans);
    }
    
    // 依据题意返回输入值
    if (ans > 6) return -1;
    return ans;
}

int main()
{
    int n;
    cin >> n;
    while (n --)
    {for (int i = 0; i < 5; ++ i) cin >> g[i];
        printf("%d\n", work());
    }
}

正文完