leetcode解题: Minesweeper (529)

发表于 | 分类于

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

You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

If a mine (‘M’) is revealed, then the game is over - change it to ‘X’.
If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
Return the board when no more squares will be revealed.
Example 1:
Input:

1
2
3
4
[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output:

1
2
3
4
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:
alt text
Example 2:
Input:

1
2
3
4
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

Output:

1
2
3
4
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:
alt text

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.

解法1：

题目看起来很复杂，其实实现起来比较简单。就一步步按照他的规则来就可以。主要是考察了DFS或者是BFS的应用。这里我用了DFS的解法，对于每一个click的方块。如果是地雷，那么直接return了。
如果不是地雷，那么统计一下周围地雷的个数。如果是空的，那么就对所有相邻的都做一遍DFS，如果是有地雷则直接范围地雷的个数。

Java

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
50
51
52
53
54
55
56
57
58
public class Solution {
    // defines the 8 directions it can point to
    private int[][] directions = {{0,1},{0,-1},{1,0},{-1,0},{-1,1},{1,1},{1,-1},{-1,-1}};
    public char[][] updateBoard(char[][] board, int[] click) {
        
        if (board.length == 0 || board[0].length == 0) {
            return board;
        }
        
        dfs(board, click[0], click[1]);
        
        return board;
        
    }
    
    private void dfs(char[][] board, int i, int j) {
        if (board[i][j] == 'M') {
            board[i][j] = 'X';
            return;
        }
        
        if (board[i][j] == 'E') {
            int n = getNumberOfMines(board, i, j);
            if (n == 0) {
                board[i][j] = 'B';
                // doing dfs for each direction
                for (int[] direction: directions) {
                    int x = i + direction[0];
                    int y = j + direction[1];
                    if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] == 'M') {
                        continue;
                    }
                    dfs(board, x, y);
                }
            } else {
                board[i][j] = (char)(n + '0');
            }
        }
        return;
    }
    
    private int getNumberOfMines(char[][] board, int i, int j) {
        int n = board.length;
        int m = board[0].length;
        int count = 0;
        for (int[] direction: directions) {
            int x = i + direction[0];
            int y = j + direction[1];
            if (x < 0 || x >= n || y < 0 || y >= m) {
                continue;
            }
            if (board[x][y] == 'M') {
                ++count;
            }
        }
        return count;
    }
}