DFS BFS的活学活用 非典型
1189. Minesweeper
带判断条件的，是否把节点放入queue in BFS。是否进行下一个的search，in DFS。
BFS:
class Solution {
public:
/**
* @param board: a board
* @param click: the position
* @return: the new board
*/
const vector<int> dx = {0, 0, -1, 1, -1, -1, 1, 1};
const vector<int> dy = {-1, 1, 0, 0, -1, 1, -1, 1};
const int dir = 8;
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
// Write your code here
// DFS
//改写为BFS。
const int m = board.size();
vector<vector<char>> res;
if(m == 0){
return res;
}
const int n = board[0].size();
//vector<vector<int>> neighbors;
std::queue<vector<int>> q;
if(board[click[0]][click[1]] == 'M'){
board[click[0]][click[1]] = 'X';
return board;
}
else{
//int cnt = 0;
q.push(click);
while(!q.empty()){
vector<int> tmp = q.front();
q.pop();
int cnt = 0;
vector<vector<int>> neighbors;
for(int i = 0; i < dir; i++){
int newX = tmp[0] + dx[i];
int newY = tmp[1] + dy[i];
if(newX < 0 || newX >= m || newY < 0 || newY >= n){
continue;
}
if(board[newX][newY] == 'M'){
cnt++;
}
if(board[newX][newY] == 'E'){
neighbors.push_back({newX, newY});
}
}
if(cnt > 0){
board[tmp[0]][tmp[1]] = '0' + cnt;
}
else{
board[tmp[0]][tmp[1]] = 'B';
for(auto nei : neighbors){
board[nei[0]][nei[1]] = 'B';//注意这里的剪枝
q.push(nei);
}
}
}
}
return board;
}
};
DFS:
class Solution {
public:
/**
* @param board: a board
* @param click: the position
* @return: the new board
*/
const vector<int> dx = {0, 0, -1, 1, -1, -1, 1, 1};
const vector<int> dy = {-1, 1, 0, 0, -1, 1, -1, 1};
const int dir = 8;
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
// Write your code here
// DFS
const int m = board.size();
vector<vector<char>> res;
if(m == 0){
return res;
}
const int n = board[0].size();
vector<vector<int>> neighbors;
if(board[click[0]][click[1]] == 'M'){
board[click[0]][click[1]] = 'X';
return board;
}
else{
int cnt = 0;
for(int i = 0; i < dir; i++){
int newX = click[0] + dx[i];
int newY = click[1] + dy[i];
if(newX < 0 || newX >= m || newY < 0 || newY >= n){
continue;
}
if(board[newX][newY] == 'M'){
cnt++;
//neighbors.push_back({newX, newY});
}
if(board[newX][newY] == 'E'){
neighbors.push_back({newX, newY});
}
}
if(cnt > 0){
board[click[0]][click[1]] = '0' + cnt;
}
else{
board[click[0]][click[1]] = 'B';
for(auto nei : neighbors){
updateBoard(board, nei);
}
}
}
return board;
}
};
Comments
Post a Comment