529. 扫雷游戏

题目描述

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

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

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

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

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

如果一个地雷（'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 <= click_r < m
0 <= click_c < n
board[click_r][click_c] 为 ‘M’ 或 ‘E’

解法一：DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


func updateBoard(board [][]byte, click []int) [][]byte {
    h, w := len(board), len(board[0])
    dirs := [][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
    var dfs func(i, j int)
    dfs = func(i, j int) {
        if board[i][j] == 'M' {
            board[i][j] = 'X'
        } else if board[i][j] == 'E' {
            // 计算相邻的地雷的数量
            mineCount := 0
            var candidates [][2]int
            for _, dir := range dirs {
                ni, nj := i+dir[0], j+dir[1]
                if 0 <= ni && ni < h && 0 <= nj && nj < w {
                    if board[ni][nj] == 'M' || board[ni][nj] == 'X' {
                        mineCount++
                    } else if board[ni][nj] == 'E' {
                        candidates = append(candidates, [2]int{ni, nj})
                    }
                }
            }
            if mineCount == 0 {
                board[i][j] = 'B'
                for _, coordinate := range candidates {
                    dfs(coordinate[0], coordinate[1])
                }
            } else {
                board[i][j] = byte('0' + mineCount)
            }
        }
    }
    dfs(click[0], click[1])
    return board
}