# C++ DFS and BFS Solution

• Minesweeper Update Board
In this problem, we are given 2D matirx of characters that represent a board.
M - Unrevealed mine
X - Revealed mine
B - Revealed blank square
E - Unrevealed Empty square
D - Revealed square with digit representing the number of mines adjacent to this square

Now, we need to follow the following rules to update the board when a click is performed
a.) If an unrevealed mine 'M' is clicked, Change that to 'X' - Game Over!
b.) If an empty square 'E' is clicked and has NO adjacent mines next to it, change it to a blank square 'B' and recursively reveal all of its adjacent unrevealed squares
c.) If an empty square 'E' is clicked and has AT LEAST 1 adjacent mine, change it to a digit square 'D' where D = number of adjacent mines
d.) Return the board when no more squares will be revealed

DFS Solution:

``````class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
int i = click[0] , j = click[1] ;
// If the click position is an 'M' change to 'X' and return
if(board[i][j] == 'M'){
board[i][j] = 'X';
}
// This means that the click position is an 'E'. Recursively update the board
else
updateRecurse(board, i, j);
return board;
}
private:
void updateRecurse(vector<vector<char>>& board, int i, int j){
int num = countAdjacentMines(board, i, j);
// Set the square to the number of adjacent mines ( if > 0 )
if(num > 0){
board[i][j] = (char)(num + '0');
}
// Set the square to a revealed blank square 'B' & Recursively update the 8 adjancent squares.
else{
board[i][j] = 'B';
for(int x=i-1; x <= i + 1; x++){
for(int y=j-1; y <= j + 1; y++){
if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || (x == i && y == j) || board[x][y] != 'E')
continue;
updateRecurse(board, x, y);
}
}
}
}
int countAdjacentMines(vector<vector<char>>& board, int i, int j){
int count = 0;
for(int x=i-1; x <= i + 1; x++){
for(int y=j-1; y <= j +1; y++){
if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || (x == i && y == j))
continue;
else if(board[x][y] == 'M'){
count++;
}
}
}
return count;
}
};
``````

BFS Solution:

``````class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
// If the click position is an 'M' change to 'X' and return
if(board[click[0]][click[1]] == 'M'){
board[click[0]][click[1]] = 'X';
return board;
}
// This means that the click position is an 'E'.
queue<vector<int>> q({click});
while(!q.empty()){
cout << q.size() << endl;
int i = q.front()[0], j = q.front()[1];
int num = countAdjacentMines(board, q.front());
// Set the square to the number of adjacent mines ( if > 0 ) or mark as blank square
board[i][j] = num > 0 ? (char)(num + '0') : 'B';
// Push adjacent, legal , unvisited squares into the queue
for(int x=i-1; num == 0 && x <= i + 1; x++){
for(int y=j-1; y <= j + 1; y++){
if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || (x == i && y == j) || board[x][y] != 'E')
continue;
vector<int> adj = {x, y};
q.push(adj);
// Mark as 'V' for now to avoid being pushed into the queue again.. actual value update in a subsequent iter
board[x][y] = 'V';
}
}
// Pop the front
q.pop();
}
return board;
}
private:

int countAdjacentMines(vector<vector<char>>& board, vector<int>& click){
int count = 0, i = click[0], j = click[1];
for(int x=i-1; x <= i + 1; x++){
for(int y=j-1; y <= j +1; y++){
if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || (x == i && y == j))
continue;
else if(board[x][y] == 'M'){
count++;
}
}
}
return count;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.