529 扫雷游戏（模拟、递归）

悠悠 2022-08-30 14:54 184阅读 0赞

**1. 问题描述：**

让我们一起来玩扫雷游戏！  
给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：  
如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。  
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。  
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。  
如果在此次点击中，若无更多方块可被揭露，则返回面板。

**示例 1：**

输入:  
\[\['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：**

输入:  
\[\['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'\]\]  
解释:  
注意：  
输入矩阵的宽和高的范围为 \[1,50\]。  
点击的位置只能是未被挖出的方块 ('M' 或者 'E')，这也意味着面板至少包含一个可点击的方块。输入面板不会是游戏结束的状态（即有地雷已被挖出）。  
简单起见，未提及的规则在这个问题中可被忽略。例如，当游戏结束时你不需要挖出所有地雷，考虑所有你可能赢得游戏或标记方块的情况。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/minesweeper

**2. 思路分析：**

感觉这道题目最关键的是需要读懂题目的意思，根据题目的要求模拟整个过程即可，主要处理的模块是递归暴露周围的方块。由题可知当我们点击的方块是地雷的时候将当前位置标记为"X"之后直接返回，如果点击的当前方块是"E"那么则需要递归挖出这个方块周围的八个方块，我们在递归前需要先标记当前这一个方块的情况，也即需要计算出相邻的八个方块中地雷的数目，如果周围相邻的八个方块存在地雷那么将当前位置标记为地雷的数目之后直接返回，否则标记为"B"，然后递归挖出周围相邻的八个方块，在往下递归的过程中如果发现当前方块不是"E"那么就可以直接return了，说明之前已经被挖过或者是存在地雷，只有当为"E"的时候才往下处理。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def dfs(self, board: List[List[str]], r: int, c: int, x: int, y: int):
            # 当前方块是"E"才往下处理
            if board[x][y] != "E": return
            s = 0
            # 计算周围相邻的八个格子的地雷数目
            for i in range(max(0, x - 1), min(x + 1, r - 1) + 1):
                for j in range(max(0, y - 1), min(y + 1, c - 1) + 1):
                    # 如果是自己那么跳过
                    if i != x or j != y:
                        if board[i][j] == "M" or board[i][j] == "X":
                            s += 1
            # 地雷的数目大于0则不往下递归暴露方块
            if s > 0:
                board[x][y] = str(s)
                return
            # 周围八个方向没有地雷则往下递归暴露周围的八个方块
            board[x][y] = "B"
            for i in range(max(0, x - 1), min(x + 1, r - 1) + 1):
                for j in range(max(0, y - 1), min(y + 1, c - 1) + 1):
                    if i != x or j != y:
                        self.dfs(board, r, c, i, j)
    
        def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
            x, y = click[0], click[1]
            r, c = len(board), len(board[0])
            # 当前方块就是的地雷
            if board[x][y] == "M":
                board[x][y] = "X"
                return board
            self.dfs(board, r, c, x, y)
            return board