TNotes.leetcode

Appearance

⏰0529. 扫雷游戏【中等】

0529. 扫雷游戏【中等】 ​

1. 📝 题目描述 ​

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

给你一个大小为 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：

img

txt
输入：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：

img

txt
输入：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'

2. 🎯 s.1 - DFS ​

c
int dirs[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

void dfs(char** board, int m, int n, int i, int j) {
    int mines = 0;
    for (int d = 0; d < 8; d++) {
        int ni = i + dirs[d][0], nj = j + dirs[d][1];
        if (ni >= 0 && ni < m && nj >= 0 && nj < n && board[ni][nj] == 'M') mines++;
    }
    if (mines > 0) { board[i][j] = '0' + mines; return; }
    board[i][j] = 'B';
    for (int d = 0; d < 8; d++) {
        int ni = i + dirs[d][0], nj = j + dirs[d][1];
        if (ni >= 0 && ni < m && nj >= 0 && nj < n && board[ni][nj] == 'E') dfs(board, m, n, ni, nj);
    }
}

char** updateBoard(char** board, int boardSize, int* boardColSize, int* click, int clickSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = boardSize;
    *returnColumnSizes = boardColSize;
    int r = click[0], c = click[1];
    if (board[r][c] == 'M') { board[r][c] = 'X'; return board; }
    dfs(board, boardSize, boardColSize[0], r, c);
    return board;
}
js
/**
 * @param {character[][]} board
 * @param {number[]} click
 * @return {character[][]}
 */
var updateBoard = function (board, click) {
  const m = board.length,
    n = board[0].length
  const [r, c] = click
  if (board[r][c] === 'M') {
    board[r][c] = 'X'
    return board
  }
  const dirs = [
    [-1, -1],
    [-1, 0],
    [-1, 1],
    [0, -1],
    [0, 1],
    [1, -1],
    [1, 0],
    [1, 1],
  ]
  const dfs = (i, j) => {
    let mines = 0
    for (const [di, dj] of dirs) {
      const ni = i + di,
        nj = j + dj
      if (ni >= 0 && ni < m && nj >= 0 && nj < n && board[ni][nj] === 'M')
        mines++
    }
    if (mines > 0) {
      board[i][j] = String(mines)
      return
    }
    board[i][j] = 'B'
    for (const [di, dj] of dirs) {
      const ni = i + di,
        nj = j + dj
      if (ni >= 0 && ni < m && nj >= 0 && nj < n && board[ni][nj] === 'E')
        dfs(ni, nj)
    }
  }
  dfs(r, c)
  return board
}
py
class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        m, n = len(board), len(board[0])
        r, c = click
        if board[r][c] == 'M':
            board[r][c] = 'X'
            return board
        dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        def dfs(i, j):
            mines = sum(1 for di, dj in dirs if 0 <= i+di < m and 0 <= j+dj < n and board[i+di][j+dj] == 'M')
            if mines > 0:
                board[i][j] = str(mines)
                return
            board[i][j] = 'B'
            for di, dj in dirs:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and board[ni][nj] == 'E':
                    dfs(ni, nj)
        dfs(r, c)
        return board
  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)

算法思路：

  • 若点击地雷，直接标记为 X
  • 否则 DFS 展开：先统计周围地雷数，若为 0 则标记 B 并继续展开邻居