LeetCode 529. Minesweeper

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/03/03/LeetCode-529-Minesweeper/

访问原文「LeetCode 529. Minesweeper

题目要求

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:

[[‘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:

  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.

题意解析

这个题指的是扫雷游戏。在扫雷游戏中,用二维矩阵标识当前的扫雷状态。没有被发掘的空块标记为'E',没有被发掘的雷为'M',发掘之后的空块标记为'N',发掘之后的块标记为'X',另外数字1-8表示该块周围有几个雷。

给出一个二维矩阵标识当天扫雷游戏的状态,然后给出下一步,求出走完下一步之后的游戏状态。

解法分析

这道题的直接使用递归就可以了,除去边界条件不谈。

如果这一步直接挖掘在已挖掘块上结束;
如果这一步直接挖掘在雷上,标记为’X’,结束;
然后计算这块周围有几个雷,雷的数目大于0则标记为对应数字并结束;雷的数目为0的话继续探索这个位置周围的8个位置。

解题代码

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
59
60
public char[][] updateBoard(char[][] board, int[] click) {
if (board.length <= 0 || board[0].length <= 0) {
return board;
}
char[][] tmpBoard = new char[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
tmpBoard[i][j] = board[i][j];
}
}
changeBoard(tmpBoard, click);
return tmpBoard;
}
private void changeBoard(char[][] board, int[] click) {
int x = click[0];
int y = click[1];
if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
return;
}
if (board[x][y] == 'M') {
board[x][y] = 'X';
return;
}
if (board[x][y] != 'E') {
return;
}
int mineNumber = (x - 1 >= 0 ? (board[x - 1][y] == 'M' ? 1 : 0) : 0)
+ (x - 1 >= 0 && y - 1 >= 0 ? (board[x - 1][y - 1] == 'M' ? 1
: 0) : 0)
+ (x - 1 >= 0 && y + 1 < board[0].length ? (board[x - 1][y + 1] == 'M' ? 1
: 0)
: 0)
+ (y - 1 >= 0 ? (board[x][y - 1] == 'M' ? 1 : 0) : 0)
+ (y + 1 < board[0].length ? (board[x][y + 1] == 'M' ? 1 : 0)
: 0)
+ (x + 1 < board.length ? (board[x + 1][y] == 'M' ? 1 : 0) : 0)
+ (x + 1 < board.length && y - 1 >= 0 ? (board[x + 1][y - 1] == 'M' ? 1
: 0)
: 0)
+ (x + 1 < board.length && y + 1 < board[0].length ? (board[x + 1][y + 1] == 'M' ? 1
: 0)
: 0);
if (mineNumber == 0) {
board[x][y] = 'B';
changeBoard(board, new int[] { x - 1, y });
changeBoard(board, new int[] { x - 1, y - 1 });
changeBoard(board, new int[] { x - 1, y + 1 });
changeBoard(board, new int[] { x, y - 1 });
changeBoard(board, new int[] { x, y + 1 });
changeBoard(board, new int[] { x + 1, y - 1 });
changeBoard(board, new int[] { x + 1, y });
changeBoard(board, new int[] { x + 1, y + 1 });
} else {
board[x][y] = (char) (mineNumber + '0');
}
}