原题地址
https://leetcode.com/problems/minesweeper/description/
题意
略
思路
简单的深度优先,根据不同情况更新。
坑点
我其实没认真玩过扫雷。。所以做完这题才知道扫雷的规则,这里说的“当一个位置不是雷,并且周围没有雷的时候,要递归地显示出这一个位置周围位置附近的雷的情况”,原来周围是包括周围8个格子的。。我一开始只朝上下左右四个方向,会少更新一些值
代码
代码里的visited
其实不需要
class Solution {
public:
void dfs(vector<vector<char>>& board , vector<vector<int>>& count, vector<vector<bool>>& visited, int x, int y) {
int m = board.size();
int n = board[0].size();
if (x < 0 || y < 0 || x >= m || y >= n ) return ;
if (visited[x][y]) return ;
visited[x][y] = true;
if (board[x][y] == 'M') {
board[x][y] = 'X';
return ;
}
if (board[x][y] >= '0' && board[x][y] <= '9') return ;
if (board[x][y] == 'E') {
if (count[x][y] == 0) {
board[x][y] = 'B';
dfs(board, count, visited, x - 1, y - 1);
dfs(board, count, visited, x - 1, y);
dfs(board, count, visited, x - 1, y + 1);
dfs(board, count, visited, x, y - 1);
dfs(board, count, visited, x, y + 1);
dfs(board, count, visited, x + 1, y - 1);
dfs(board, count, visited, x + 1, y );
dfs(board, count, visited, x + 1, y + 1);
// dfs(board, count, visited, x + 1, y);
// dfs(board, count, visited, x - 1, y);
// dfs(board, count, visited, x, y + 1);
// dfs(board, count, visited, x, y - 1);
} else {
board[x][y] = (char)(count[x][y] + '0');
}
}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
if (click.empty()) return board;
vector<vector<char>> result;
if (board.empty()) return result;
int m = board.size();
int n = board[0].size();
vector<vector<int>> count(m, vector<int>(n, 0));
vector<vector<bool>> visited(m, vector<bool>(n, false));
countMinesAround(board, count);
dfs(board, count, visited, click[0], click[1]);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << count[i][j] << " ";
}
cout << endl;
}
return board;
}
void countMinesAround(vector<vector<char>>& board, vector<vector<int>>& count) {
int m = board.size();
int n = board[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i - 1 >= 0 && j - 1 >= 0) {
count[i][j] += (board[i - 1][j - 1] == 'M' ? 1 : 0);
}
if (i - 1 >= 0) {
count[i][j] += (board[i - 1 ][j ] == 'M' ? 1 : 0);
}
if (i - 1 >= 0 && j + 1 < n) {
count[i][j] += (board[i - 1][j + 1] == 'M' ? 1 : 0);
}
if (j - 1 >= 0) {
count[i][j] += (board[i ][j - 1] == 'M' ? 1 : 0);
}
if (j + 1 >= 0) {
count[i][j] += (board[i ][j + 1] == 'M' ? 1 : 0);
}
if (i + 1 < m && j - 1 >= 0) {
count[i][j] += (board[i + 1][j - 1] == 'M' ? 1 : 0);
}
if (i + 1 < m) {
count[i][j] += (board[i + 1][j] == 'M' ? 1 : 0);
}
if (i + 1 < m && j + 1 < n) {
count[i][j] += (board[i + 1][j + 1] == 'M' ? 1 : 0);
}
}
}
}
};