扫雷游戏

标签: 深度优先搜索 广度优先搜索 数组 矩阵

难度: Medium

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

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

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

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

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

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

示例 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'

Submission

运行时间: 30 ms

内存: 16.7 MB

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:

        def dfs(board, i, j):
            if board[i][j] != 'E':
                return

            cnt = 0
            for k in range(8):
                l, r = i + dir_xy[k][0], j + dir_xy[k][1]
                if 0 <= l < m and 0 <= r < n and board[l][r] == 'M':
                    cnt += 1

            if cnt > 0:
                board[i][j] = str(cnt)
            else:
                board[i][j] = 'B'
                for k_ in range(8):
                    l_, r_ = i + dir_xy[k_][0], j + dir_xy[k_][1]
                    if 0 <= l_ < m and 0 <= r_ < n:
                        dfs(board, l_, r_)

        m, n = len(board), len(board[0])
        dir_xy = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
        i, j = click[0], click[1]
        
        if board[i][j] == 'M':
            board[i][j] = 'X'
        else:
            dfs(board, i, j)
        
        return board

Explain

这个题解采用深度优先搜索（DFS）的思路来解决扫雷游戏问题。首先判断点击位置是否是地雷，如果是则直接将其标记为 'X'。否则，进入 DFS 函数进行递归处理。在 DFS 函数中，首先判断当前位置是否为未挖出的空方块 'E'，如果不是则直接返回。然后统计当前位置周围8个方向上的地雷数量。如果地雷数量大于0，则将当前位置更新为地雷数量。如果地雷数量为0，则将当前位置更新为 'B'，并递归处理周围8个方向上的未挖出方块。

时间复杂度: O(m*n)

空间复杂度: O(m*n)

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:

        def dfs(board, i, j):
            if board[i][j] != 'E':  # 如果当前位置不是未挖出的空方块，直接返回
                return

            cnt = 0
            for k in range(8):  # 统计周围8个方向上的地雷数量
                l, r = i + dir_xy[k][0], j + dir_xy[k][1]
                if 0 <= l < m and 0 <= r < n and board[l][r] == 'M':
                    cnt += 1

            if cnt > 0:  # 如果周围有地雷，将当前位置更新为地雷数量
                board[i][j] = str(cnt)
            else:  # 如果周围没有地雷，将当前位置更新为 'B'，并递归处理周围的未挖出方块
                board[i][j] = 'B'
                for k_ in range(8):
                    l_, r_ = i + dir_xy[k_][0], j + dir_xy[k_][1]
                    if 0 <= l_ < m and 0 <= r_ < n:
                        dfs(board, l_, r_)

        m, n = len(board), len(board[0])
        dir_xy = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]  # 8个方向的偏移量
        i, j = click[0], click[1]  # 点击位置的坐标
        
        if board[i][j] == 'M':  # 如果点击位置是地雷，将其标记为 'X'
            board[i][j] = 'X'
        else:  # 如果点击位置不是地雷，进行 DFS 递归处理
            dfs(board, i, j)
        
        return board

Explore

在DFS的实现中，每次递归前都会检查当前方块是否是未挖出的空方块（'E'）。只有当方块状态为'E'时，才会进行处理和递归调用。如果方块已经标记为数字或'B'，则这个检查会导致直接返回，避免对其进行重复处理。这样确保了每个方块在整个递归过程中只被处理一次。

递归终止条件是基于当前方块的状态。如果当前方块不是未挖出的空方块（'E'），递归就会停止。这包括已经被标记为数字或'B'的方块，以及初始已经是地雷（'M'）的方块。这种条件确保了递归只在有可能继续展开的空白方块上进行，从而避免无效的递归调用。

当一个方块周围的地雷数量为0时，说明其周围8个方向都没有地雷，因此这些方向上的方块也都是安全的。按照扫雷游戏的规则，这时不仅需要将当前方块更新为'B'表示无地雷，还需要递归检查周围的方块，以便快速打开周围的安全区域。这种递归逻辑是为了扩展玩家的安全可行动区域，提高游戏的可玩性和效率。

在这个题解中，当点击位置是地雷时，只将点击的那个地雷标记为'X'，表示游戏结束。题解中没有提到修改其他地雷的显示状态，这通常意味着只显示玩家点击的那个地雷。在实际的游戏中，是否显示所有地雷通常取决于具体的游戏设计，有些版本可能在游戏结束时显示所有地雷，而有些则只显示触发的那个。