M529.扫雷游戏

dfs, bfs, https://leetcode.cn/problems/minesweeper/

让我们一起来玩扫雷游戏！

给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中：

'M' 代表一个 未挖出的 地雷，
'E' 代表一个 未挖出的 空方块，
'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，
数字（'1' 到 '8'）表示有多少地雷与这块 已挖出的 方块相邻，
'X' 则表示一个 已挖出的 地雷。

给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（'M' 或者 'E'）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。

根据以下规则，返回相应位置被点击后对应的盘面：

如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X' 。
如果一个 没有相邻地雷 的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
如果一个 至少与一个地雷相邻 的空方块（'E'）被挖出，修改它为数字（'1' 到 '8' ），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回盘面。

示例 1：

输入：board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0]
输出：[["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

示例 2：

输入：board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2]
输出：[["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 50
board[i][j] 为 'M'、'E'、'B' 或数字 '1' 到 '8' 中的一个
click.length == 2
0 <= clickr < m
0 <= clickc < n
board[clickr][clickc] 为 'M' 或 'E'

这个问题可以通过深度优先搜索 (DFS) 或 广度优先搜索 (BFS) 来模拟扫雷游戏的逻辑。

核心规则分析：

点击地雷 ('M')：直接将其改为 'X'，游戏结束，返回盘面。
点击空方块 ('E')：
- 统计其周围 8 个方向相邻的地雷数量。
- 如果地雷数 > 0：将当前方块改为该数字（如 '1' 到 '8'），停止递归。
- 如果地雷数 == 0：将当前方块改为 'B'（表示已挖出的空白），并递归地揭露周围 8 个方向所有未挖出的方块 ('E')。
算法实现 (DFS 方案)：

python

from typing import List

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        r, c = click[0], click[1]
        
        # 规则 1：如果点击的是地雷 'M'
        if board[r][c] == 'M':
            board[r][c] = 'X'
            return board
        
        # 如果点击的不是 'E'（比如点击了数字或 'B'），按规则不需要处理
        if board[r][c] != 'E':
            return board
            
        rows, cols = len(board), len(board[0])
        
        def dfs(i, j):
            # 边界检查及是否为未挖出的空方块 'E'
            if not (0 <= i < rows and 0 <= j < cols) or board[i][j] != 'E':
                return
            
            # 统计相邻的 8 个方向的地雷 'M' 数量
            mine_count = 0
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    if di == 0 and dj == 0:
                        continue
                    ni, nj = i + di, j + dj
                    if 0 <= ni < rows and 0 <= nj < cols and board[ni][nj] == 'M':
                        mine_count += 1
            
            if mine_count > 0:
                # 规则 3：如果周围有雷，显示数字，不再继续递归
                board[i][j] = str(mine_count)
            else:
                # 规则 2：如果周围没雷，显示 'B'，并递归相邻的 'E'
                board[i][j] = 'B'
                for di in range(-1, 2):
                    for dj in range(-1, 2):
                        if di == 0 and dj == 0:
                            continue
                        dfs(i + di, j + dj)
        
        dfs(r, c)
        return board

复杂度分析：

时间复杂度 $O (M \times N)$ ：其中 $M$ 和 $N$ 是棋盘的行数和列数。在最坏情况下（例如整个棋盘都没有地雷），我们可能需要访问每一个格子。
空间复杂度 $O (M \times N)$ ：主要取决于递归调用的深度，最坏情况下递归栈的大小会达到 $M \times N$ 。

关键点说明：

为什么不递归 'M'：在统计相邻地雷时，我们只统计 'M'，但递归揭露时只揭露 'E'。这是因为根据游戏逻辑，如果一个格子周围有 'M'，它的 mine_count 一定大于 0，它会被标记为数字并停止递归，所以程序永远不会从一个 'B' 自动递归到一个 'M'。
搜索方向：扫雷是 8 个方向（包含对角线），所以循环范围是 range(-1, 2)。
终止条件：board[i][j] != 'E' 是 DFS 的关键终止条件，它既防止了重复访问（死循环），也符合只揭露未揭露方块的规则。

M529.扫雷游戏 ​

M529.扫雷游戏