Description
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.
Example1
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:
Example2
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.
Discussion
给定扫雷游戏的一个当前状态，求点击某个格子之后的状态。
这个问题基本跟着游戏规则一步步进行就好了，而这里需要采用DFS对第3条规则的情况中的相邻的8个格子进行遍历。
C++ Code
class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
//1. 如果当前按的位置是一个雷，直接标X返回
if(board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}
dfs(board, click[0], click[1]);
return board;
}
void dfs(vector<vector<char>> & board, int curX, int curY) {
int mineCount = 0; //周围雷数
//adjacent表示当前位置周围的8个方向
int adjacent[8][2] = {
{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}
};
//统计一下当前按的位置周围的雷数
for (int i = 0; i < 8; i++) {
if(inBoard(board, curX + adjacent[i][0], curY + adjacent[i][1])) {
if (board[curX + adjacent[i][0]][curY + adjacent[i][1]] == 'M') {
mineCount ++;
}
}
}
//2. 如果当前按的位置周围有雷，把该格子设置为雷数
if (mineCount > 0) {
board[curX][curY] = '0' + mineCount;
return;
}
//3. 如果当前按的位置周围没有雷，将该位置置为B，递归查看周围8个未翻的格子
board[curX][curY] = 'B';
for (int i = 0; i < 8; i++) {
if (inBoard(board, curX + adjacent[i][0], curY + adjacent[i][1]) && board[curX + adjacent[i][0]][curY + adjacent[i][1]] == 'E') {
dfs(board, curX + adjacent[i][0], curY + adjacent[i][1]);
}
}
}
/**
判断该位置是否在给定的面板内
@param board 游戏面板
@param x x坐标
@param y y坐标
@return 是否在面板内
*/
bool inBoard(vector<vector<char>> & board, int x, int y) {
if(x < 0 || x > board.size() - 1 || y < 0 || y > board[0].size() - 1) {
return false;
} else {
return true;
}
}
};