Leetcode刷题详解——扫雷游戏

1. 题目链接：529. 扫雷游戏

2. 题目描述：

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

给你一个大小为 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"]]
1
2

示例 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"]]
1
2

提示：

• 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'

3. 解法：

模拟类型的dfs题目，首先要搞懂题目的要求，也就是游戏规则，从题目所给的点击位置开始，根据游戏规则，来一次dfs即可。

1. 首先，定义了两个数组dx和dy，分别表示八个方向的横坐标偏移量和纵坐标偏移量。
2. 然后，在updateBoard函数中，获取了棋盘的行数m和列数n，以及点击位置的坐标(x, y)。
3. 如果点击位置是地雷（即board[x][y] == 'M'），则将该位置标记为已点击（即board[x][y] = 'X'），并返回更新后的棋盘。
4. 如果点击位置不是地雷，则调用dfs函数进行深度优先搜索。
5. dfs函数的作用是计算一个位置周围的地雷数量，并将该位置标记为相应的数字或字符。具体步骤如下：
   • 初始化周围地雷的数量为0。
   • 遍历八个方向，计算相邻位置的坐标，并判断是否在棋盘范围内且为地雷。如果是，则地雷数量加1。
   • 如果周围有地雷，则将当前位置标记为周围地雷的数量，并返回。
   • 如果周围没有地雷，则将当前位置标记为未点击（即board[i][j] = 'B'）。
   • 再次遍历八个方向，计算相邻位置的坐标，并判断是否在棋盘范围内且为未点击的空位。如果是，则对相邻位置进行深度优先搜索。
6. 最后，返回更新后的棋盘。

class Solution {
    int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}; // 定义八个方向的横坐标偏移量
    int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1}; // 定义八个方向的纵坐标偏移量
    int m, n; // 定义棋盘的行数和列数

public:
    vector> updateBoard(vector>& board, vector& click) {
        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); // 否则，进行深度优先搜索
        return board; // 返回更新后的棋盘
    }

    void dfs(vector>& board, int i, int j) // 深度优先搜索函数
    {
        int count = 0; // 初始化周围地雷的数量为0
        for (int k = 0; k < 8; k++) // 遍历八个方向
        {
            int x = i + dx[k], y = j + dy[k]; // 计算相邻位置的坐标
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') // 如果相邻位置是地雷
            {
                count++; // 地雷数量加1
            }
        }
        if (count) // 如果周围有地雷
        {
            board[i][j] = count + '0'; // 将当前位置标记为周围地雷的数量
            return; // 返回
        }
        else // 如果周围没有地雷
        {
            board[i][j] = 'B'; // 将当前位置标记为未点击
            for (int k = 0; k < 8; k++) // 遍历八个方向
            {
                int x = i + dx[k], y = j + dy[k]; // 计算相邻位置的坐标
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') // 如果相邻位置是未点击的空位
                {
                    dfs(board, x, y); // 对相邻位置进行深度优先搜索
                }
            }
        }
    }
};

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49