解谜游戏题解

密室逃脱密码锁问题题解

题目描述

小张在密室逃脱的游戏中需要通过解开密码锁来获取线索。密码锁是一个 n x m 的网格，每个格子里有一个按钮和一个灯。初始状态下，灯可能是亮的或者灭的。

按下某个按钮会导致该按钮的灯以及其上下左右相邻按钮的灯状态发生翻转（亮变灭，灭变亮）。小张的任务是通过最少次数的按键，使得所有灯全部熄灭。

输入

• 第一行包含两个整数 n 和 m，表示网格的行数和列数。
• 接下来的 n 行，每行是一个长度为 m 的01字符串，0 表示灯灭，1 表示灯亮。

输出

• 一行一个整数，表示最少按几次按钮可以把灯全部熄灭。

题解思路

1. 状态表示

我们使用一个 n x m 的二维数组来表示灯的状态，1 表示灯亮，0 表示灯灭。每按下一个按钮，都会影响到该按钮以及其上下左右四个方向的按钮。

2. 枚举第一行的所有按法

由于每个按钮可以按或不按，因此第一行的所有可能按法共有 (2^m) 种。我们可以通过枚举所有这些可能性来尝试找到一种按法，使得在最少按键次数下，最终所有灯都熄灭。

3. 动态模拟按按钮

对于每一种按法，计算它对第一行产生的影响，并推导出对整个网格的影响。我们逐行更新网格的灯状态，直到处理完最后一行。如果最后一行的灯全部熄灭，则该按法是有效的。

4. 选择最优解

在所有可能的第一行按法中，选择使灯全部熄灭的按键次数最少的一种，作为最终的解。

代码实现

以下是基于上述思路的代码实现：

#include <iostream>
#include <climits>

using namespace std;

int n, m;
int grid[16][16];  // 存储初始灯的状态
int tmp[16][16];   // 用于模拟按钮按下后的灯的状态

// 按下某个按钮后，改变其四周和自己的灯状态
void flip(int x, int y) {
    tmp[x][y] ^= 1; // 翻转自己
    if (x > 0) tmp[x-1][y] ^= 1; // 上
    if (x < n-1) tmp[x+1][y] ^= 1; // 下
    if (y > 0) tmp[x][y-1] ^= 1; // 左
    if (y < m-1) tmp[x][y+1] ^= 1; // 右
}

int solve() {
    int minSteps = INT_MAX;
    
    // 枚举第一行的按法，共有2^m种可能
    for (int firstRow = 0; firstRow < (1 << m); ++firstRow) {
        // 将初始状态复制到临时状态
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                tmp[i][j] = grid[i][j];
        
        int steps = 0;
        // 应用第一行的按法
        for (int j = 0; j < m; ++j) {
            if (firstRow & (1 << j)) {
                flip(0, j);
                steps++;
            }
        }
        
        // 根据第一行的结果，决定后续的按法
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (tmp[i-1][j] == 1) { // 如果上一行的灯还亮着，就需要按当前这一行的按钮
                    flip(i, j);
                    steps++;
                }
            }
        }
        
        // 检查最后一行是否全部熄灭
        bool allOff = true;
        for (int j = 0; j < m; ++j) {
            if (tmp[n-1][j] == 1) {
                allOff = false;
                break;
            }
        }
        
        if (allOff) {
            minSteps = min(minSteps, steps);
        }
    }
    
    return minSteps;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        string line;
        cin >> line;
        for (int j = 0; j < m; ++j) {
            grid[i][j] = line[j] - '0';
        }
    }
    
    cout << solve() << endl;
    
    return 0;
}

复杂度分析

• 枚举第一行的可能性为 (2^m)，每次按法的复杂度为 (O(n \times m))。
• 总时间复杂度为 (O(2^m \times n \times m))，在题目给定的限制范围内可行。

总结

通过枚举第一行的按法并动态模拟按按钮后的网格变化，我们能够找到最少按键次数以熄灭所有灯。这个方法在时间复杂度上是可接受的，并能够高效地解决问题。