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'

解题思路

这道题是经典的矩阵搜索问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。

核心思路：

  1. 首先判断点击位置是否为地雷，如果是则直接标记为 ‘X’ 并返回
  2. 如果是空方块，则统计周围8个方向的地雷数量
  3. 如果周围有地雷，则将当前位置标记为地雷数量（数字字符）
  4. 如果周围没有地雷，则将当前位置标记为 ‘B’，并递归处理所有相邻的未挖出方块

算法流程：

  1. 定义8个方向的偏移量数组
  2. 从点击位置开始，使用DFS进行搜索
  3. 对于每个位置，先检查是否越界或已被访问
  4. 统计周围地雷数量，根据数量决定当前格子的状态
  5. 如果当前格子标记为 ‘B’（无相邻地雷），则递归处理所有相邻格子

推荐解法： 使用DFS，代码简洁且逻辑清晰，空间复杂度较低（只使用递归栈）。

代码实现

class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int m = board.size(), n = board[0].size();
        int x = click[0], y = click[1];
        
        // 如果点击到地雷，游戏结束
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
            return board;
        }
        
        dfs(board, x, y, m, n);
        return board;
    }
    
private:
    vector<vector<int>> directions = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    
    void dfs(vector<vector<char>>& board, int x, int y, int m, int n) {
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'E') {
            return;
        }
        
        // 统计周围地雷数量
        int mineCount = 0;
        for (auto& dir : directions) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'M') {
                mineCount++;
            }
        }
        
        if (mineCount > 0) {
            // 有相邻地雷，标记数量
            board[x][y] = '0' + mineCount;
        } else {
            // 没有相邻地雷，标记为B并递归搜索
            board[x][y] = 'B';
            for (auto& dir : directions) {
                dfs(board, x + dir[0], y + dir[1], m, n);
            }
        }
    }
};

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        m, n = len(board), len(board[0])
        x, y = click[0], click[1]
        
        # 如果点击到地雷，游戏结束
        if board[x][y] == 'M':
            board[x][y] = 'X'
            return board
        
        directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        
        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >= n or board[x][y] != 'E':
                return
            
            # 统计周围地雷数量
            mine_count = 0
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'M':
                    mine_count += 1
            
            if mine_count > 0:
                # 有相邻地雷，标记数量
                board[x][y] = str(mine_count)
            else:
                # 没有相邻地雷，标记为B并递归搜索
                board[x][y] = 'B'
                for dx, dy in directions:
                    dfs(x + dx, y + dy)
        
        dfs(x, y)
        return board

public class Solution {
    private int[][] directions = new int[][] {
        new int[]{-1,-1}, new int[]{-1,0}, new int[]{-1,1},
        new int[]{0,-1}, new int[]{0,1},
        new int[]{1,-1}, new int[]{1,0}, new int[]{1,1}
    };
    
    public char[][] UpdateBoard(char[][] board, int[] click) {
        int m = board.Length, n = board[0].Length;
        int x = click[0], y = click[1];
        
        // 如果点击到地雷，游戏结束
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
            return board;
        }
        
        DFS(board, x, y, m, n);
        return board;
    }
    
    private void DFS(char[][] board, int x, int y, int m, int n) {
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'E') {
            return;
        }
        
        // 统计周围地雷数量
        int mineCount = 0;
        foreach (var dir in directions) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'M') {
                mineCount++;
            }
        }
        
        if (mineCount > 0) {
            // 有相邻地雷，标记数量
            board[x][y] = (char)('0' + mineCount);
        } else {
            // 没有相邻地雷，标记为B并递归搜索
            board[x][y] = 'B';
            foreach (var dir in directions) {
                DFS(board, x + dir[0], y + dir[1], m, n);
            }
        }
    }
}

var updateBoard = function(board, click) {
    const m = board.length, n = board[0].length;
    const [x, y] = click;
    
    // 如果点击到地雷，游戏结束
    if (board[x][y]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m×n)最坏情况下需要访问所有格子
空间复杂度O(m×n)递归栈深度最大为 m×n

相关题目