LeetCode 529. 扫雷游戏

题目描述

给你一个大小为 m x n 的二维字符矩阵 board，表示一个扫雷游戏的棋盘。矩阵中的字符含义如下：

• 'M' 代表一个 未挖出的 地雷。
• `'E'** 代表一个 未挖出的 空方块。
• 'B' 代表一个 已挖出的，且周围（上，下，左，右，左上，右上，左下，右下）没有地雷的空方块。
• 数字（'1' 到 '8'）代表一个 已挖出的，且周围地雷数量的方块。
• 'X' 代表一个 已挖出的 地雷。

现在，你根据以下规则，在一次点击位置 (click[0], click[1]) 后，返回更新后的棋盘。

点击规则：

1. 如果一个地雷（'M'）被挖出，游戏就结束了，你将它改为 'X'。
2. 如果一个 至少有一个相邻地雷 的空方块（'E'）被挖出，你将它修改为数字（'1' 到 '8'），表示周围地雷的数量。
3. 如果一个 没有相邻地雷 的空方块（'E'）被挖出，你将它修改为 'B'，并且 所有相邻的未挖出方块（'E'）都应该被递归地揭露。

解题过程

这个问题的核心在于规则3：当点击一个周围没有地雷的方块时，需要自动揭露所有相邻的方块，并且这个过程是递归的。这非常适合使用 深度优先搜索（DFS） 或 广度优先搜索（BFS） 算法来解决。我们将使用DFS进行讲解。

第一步：定义辅助函数和方向数组

首先，我们需要一个方便的方法来遍历一个方块的8个相邻方向（上、下、左、右、左上、右上、左下、右下）。我们可以定义一个方向数组。

# 定义8个可能的方向：上、下、左、右、左上、右上、左下、右下
directions = [(-1, -1), (-1, 0), (-1, 1),
              (0, -1),           (0, 1),
              (1, -1),  (1, 0),  (1, 1)]

第二步：实现核心的DFS函数

我们将实现一个递归函数 dfs(board, x, y)，它的作用是从位置 (x, y) 开始，根据规则更新棋盘。

1. 边界条件检查：首先检查 (x, y) 是否在棋盘范围内。如果不在，直接返回。
2. 处理当前方块：
   • 如果当前方块是 'M'（地雷），根据规则1，将其改为 'X'，然后返回。这代表游戏结束。
   • 如果当前方块是 'E'（未挖出的空方块），我们需要计算它周围8个方向的地雷数量。
3. 计算周围地雷数量：
   • 初始化一个计数器 count = 0。
   • 遍历8个方向，对于每个相邻位置 (nx, ny)，检查它是否是地雷（'M' 或 'X'）。如果是，count 加1。
4. 根据地雷数量决定下一步行动：
   • 情况A：count > 0。根据规则2，将当前方块 board[x][y] 更新为表示地雷数量的字符（例如，str(count)）。然后停止，不再向周围递归。因为规则只要求揭露当前方块。
   • 情况B：count == 0。根据规则3，将当前方块 board[x][y] 更新为 'B'。然后，递归地揭露所有相邻的未挖出方块。也就是遍历8个方向，对每一个相邻的 'E' 方块调用 dfs 函数。

第三步：处理初始点击

在主函数中，我们获取点击的坐标 (r, c)。

1. 首先检查点击位置 (r, c) 的原始字符。
2. 如果它直接就是 'M'，根据规则1，将其改为 'X'，然后返回棋盘。
3. 否则，它就是 'E'。我们从这一点开始调用 dfs 函数。

详细步骤示例

假设我们有一个棋盘和一次点击：

棋盘（初始）:
[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

点击: [3, 0]

1. 初始点击：点击 (3, 0)，这是一个 'E'。我们调用 dfs(board, 3, 0)。
2. 第一层DFS：在 (3, 0)。
   • 计算周围地雷数量。检查它的8个邻居（例如 (2, -1) 越界忽略，(2, 0) 是 'E'，(2, 1) 是 'E'，(3, -1) 越界忽略，(3, 1) 是 'E'，(4, -1) 越界忽略，(4, 0) 越界忽略，(4, 1) 越界忽略）。没有发现地雷 ('M')，所以 count = 0。
   • 因为 count == 0，将 board[3][0] 设为 'B'。
   • 然后递归访问它的所有有效且为 'E' 的邻居。这里会递归调用 dfs(board, 2, 0) 和 dfs(board, 2, 1) 和 dfs(board, 3, 1)。
3. 第二层DFS（以 dfs(board, 2, 0) 为例）：
   • 计算 (2, 0) 周围地雷数量。检查它的邻居（例如 (1, -1) 越界，(1, 0) 是 'E'，(1, 1) 是 'E'，(2, -1) 越界，(2, 1) 是 'E'，(3, -1) 越界，(3, 0) 现在是 'B'（已挖出，不算地雷），(3, 1) 是 'E'）。没有发现地雷，count = 0。
   • 将 board[2][0] 设为 'B'。
   • 递归访问它的未挖出邻居 (1, 0), (1, 1), (2, 1), (3, 1)。注意 (3, 0) 已是 'B'，不再访问。
4. 过程继续：这个DFS过程会像涟漪一样扩散开来，直到遇到有地雷相邻的方块（被标记为数字）或者棋盘边界。
5. 最终结果：所有与初始点击点相连的、且路径上不遇到地雷的空白区域都会被揭露。

最终棋盘可能如下：

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

总结
这个算法通过深度优先搜索，模拟了扫雷游戏中的点击揭露逻辑。关键在于区分两种情况：当周围有地雷时，只更新当前方块；当周围没有地雷时，更新当前方块并递归地处理所有相邻的未挖出方块，从而实现连锁揭露的效果。