[LeetCode] 529. Minesweeper

Let’s play the minesweeper game (Wikipedia, online game)!

You are given an m x n char matrix board representing the game board where:

‘M’ represents an unrevealed mine,
‘E’ represents an unrevealed empty square,
‘B’ represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),
digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and
‘X’ represents a revealed mine.

You are also given an integer array click where click = [clickr, clickc] represents the next click position among all the unrevealed squares (‘M’ or ‘E’).

Return the board after revealing this position according to the following rules:

1. The range of the input matrix’s height and width is [1,50].
2. The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.
3. The input board won’t be a stage when game is over (some mines have been revealed).
4. For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

Example 1:
Input:

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output:

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Example 2:
Input:

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

Output:

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Note:
The range of the input matrix’s height and width is [1,50].
The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.

The input board won’t be a stage when game is over (some mines have been revealed).

For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

扫雷游戏。

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

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

‘M’ 代表一个 未挖出的 地雷，
‘E’ 代表一个 未挖出的 空方块，
‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，
数字（’1’ 到 ‘8’）表示有多少地雷与这块 已挖出的 方块相邻，
‘X’ 则表示一个 已挖出的 地雷。
给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（’M’ 或者 ‘E’）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。

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

如果一个地雷（’M’）被挖出，游戏就结束了- 把它改为 ‘X’ 。
如果一个 没有相邻地雷 的空方块（’E’）被挖出，修改它为（’B’），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
如果一个 至少与一个地雷相邻 的空方块（’E’）被挖出，修改它为数字（’1’ 到 ‘8’ ），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回盘面。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minesweeper
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

游戏本身我们小时候应该都玩过，我这里提炼以下题目里面的字母和规则吧。

M - 未发现的雷
E - 未发现的空白方块
B - 发现的空白方块
数字 1 - 8
X - 发现了的雷

这个题我做的时候个人觉得规则解释的不是非常明确，虽然题目说了没有提到的规则可以被忽略（Note 4）。题目给的是二维矩阵 board 和其中的某一个坐标 click。如果当前 click 位置上点开是个雷，把他 mark 成 X，然后直接就返回 board 了。例子二把周围的八个坐标 mark 成了 1，但是如果你只是 mark 了雷而不 mark 那些 1，也是可以的。另外，比如第一个例子，点开的坐标背后是一个B，但是实际题目要求你是递归地遍历完整个 board，这个跟我们小时候玩游戏的时候有一点区别，因为他点一次，直接就要求你把整个 board 的结果返回了。但是雷正上方的那个坐标却依然保持了 E。这个坐标保持E的原因是在于 DFS 遍历的时候先找到了雷所以就直接返回 board 了，还没来得及去看那个坐标。

回到这道题的解题思路上。既然题目提示了 recursively，那么我们试着用 DFS 做。不过这道题不同于一般的 DFS 题，需要遍历当前坐标周围的八个邻居。

如果当前坐标是雷，标记成X，立马返回 board
如果当前坐标不是雷，遍历其八个邻居，计算一下有几个雷，把雷的数量写在当前坐标上，返回 board
如果当前坐标是 blank/E，则把当前坐标改成 B，然后递归去看他的八个邻居

复杂度

时间O(mn)
空间O(n)

代码

Java实现

class Solution {
    int[][] dirs = new int[][] {{-1, 1}, {-1, 0}, {-1, -1}, {0, 1}, {0, -1}, {1, 1}, {1, 0}, {1, -1}};
    int m;
    int n;

    public char[][] updateBoard(char[][] board, int[] click) {
        m = board.length;
        n = board[0].length;
        int i = click[0];
        int j = click[1];
        if (board[i][j] == 'M' || board[i][j] == 'X') {
            board[i][j] = 'X';
            return board;
        }

        int nums = 0;
        for (int[] dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {
                nums++;
            }
        }

        // mark the number of bombs
        if (nums > 0) {
            board[i][j] = (char) (nums + '0');
            return board;
        }

        // if no bomb, mark it blank
        board[i][j] = 'B';
        for (int[] dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {
                updateBoard(board, new int[] { x, y });
            }
        }
        return board;
    }
}