# Java Solution, DFS + BFS

• This is a typical `Search` problem, either by using `DFS` or `BFS`. Search rules:

1. If click on a mine ('`M`'), mark it as '`X`', stop further search.
2. If click on an empty cell ('`E`'), depends on how many surrounding mine:
2.1 Has surrounding mine(s), mark it with number of surrounding mine(s), stop further search.
2.2 No surrounding mine, mark it as '`B`', continue search its `8` neighbors.

DFS solution.

``````public class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length, n = board[0].length;
int row = click[0], col = click[1];

if (board[row][col] == 'M') { // Mine
board[row][col] = 'X';
}
else { // Empty
// Get number of mines first.
int count = 0;
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'M' || board[r][c] == 'X') count++;
}
}

if (count > 0) { // If it is not a 'B', stop further DFS.
board[row][col] = (char)(count + '0');
}
else { // Continue DFS to adjacent cells.
board[row][col] = 'B';
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'E') updateBoard(board, new int[] {r, c});
}
}
}
}

return board;
}
}
``````

BFS solution. As you can see the basic logic is almost the same as DFS. Only added a queue to facilitate BFS.

``````public class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length, n = board[0].length;

while (!queue.isEmpty()) {
int[] cell = queue.poll();
int row = cell[0], col = cell[1];

if (board[row][col] == 'M') { // Mine
board[row][col] = 'X';
}
else { // Empty
// Get number of mines first.
int count = 0;
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'M' || board[r][c] == 'X') count++;
}
}

if (count > 0) { // If it is not a 'B', stop further BFS.
board[row][col] = (char)(count + '0');
}
else { // Continue BFS to adjacent cells.
board[row][col] = 'B';
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'E') {
board[r][c] = 'B'; // Avoid to be added again.
}
}
}
}
}
}

return board;
}
}
``````

• Great Solution! Thanks!

• @shawngao you and set board[r][c] = 'B' after adding it to queue to avoid using visited array.

• @jordandong Yes. Updated my post.

• @shawngao In code: ``` if (board[r][c] == 'M' || board[r][c] == 'X') count++; ```, is `board[r][c] == 'X'` needed ?

• @readman Not really. I put it there for sake of safety during contest. 1 bug = 10 min penalty :)

• Thanks for sharing! Here is my solution with some helper method.

``````    public char[][] updateBoard(char[][] board, int[] click) {
if (board.length == 0 || board[0].length == 0 || click.length != 2) return board;
int x = click[0], y = click[1], m = board.length, n = board[0].length;
if (board[x][y] == 'M') {
board[x][y] = 'X';
} else {
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
dfs(board, x, y, m, n, dirs);
}
return board;
}

private void dfs(char[][] board, int x, int y, int m, int n, int[][] dirs) {
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'E') return;
int mine = adjMine(board, x, y, m, n);
if (mine > 0) {
board[x][y] = (char) ('0' + mine);
} else {
board[x][y] = 'B';
for (int[] d : dirs) {
dfs(board, x + d[0], y + d[1], m, n, dirs);
}
}
}

private int adjMine(char[][] board, int x, int y, int m, int n) {
int cnt = 0;
for (int i = x - 1; i <= x + 1; i++) {
for (int j = y - 1; j <= y + 1; j++) {
if (0 <= i && i < m && 0 <= j && j < n && board[i][j] == 'M')
cnt++;
}
}
return cnt;
}
``````

• Another BFS -

``````public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length;
if (m == 0) return board;
int n = board[0].length;

int[][] dir = {{-1, 0},{-1, 1},{0, 1},{1,1},{1, 0},{1, -1},{0, -1}, {-1, -1}};

int X = 0, Y = 0, newX = 0, newY = 0, cnt = 0;

q1.offer(click);

while (!q1.isEmpty()) {
X = q1.peek()[0]; Y = q1.poll()[1];
switch (board[X][Y]) {
case 'M' :
board[X][Y] = 'X';
return board;
case 'E' :
cnt = 0;
q2.clear();
for (int i = 0; i < 8; i++) {
newX = X + dir[i][0];
newY = Y + dir[i][1];
if (0 <= newX && newX < m && 0 <= newY && newY < n) {
if (board[newX][newY] == 'M') cnt++;
if (board[newX][newY] == 'E') q2.offer(new int[]{newX, newY});
}
}
if (cnt == 0) {
board[X][Y] = 'B';
} else board[X][Y] = Character.forDigit(cnt, 10);
break;
}
}
return board;``````

• DFS solution：

···

``````private int hasMine(char[][] board, int i, int j) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length)
return 0;
return board[i][j] == 'M' ? 1 : 0;
}

private int findAdjMineNum(char[][] board, int i, int j) {
return hasMine(board, i - 1, j - 1) +
hasMine(board, i - 1, j) +
hasMine(board, i - 1, j + 1) +
hasMine(board, i, j - 1) +
hasMine(board, i, j + 1) +
hasMine(board, i + 1, j - 1) +
hasMine(board, i + 1, j) +
hasMine(board, i + 1, j + 1);
}

private void updateOneSquare(char[][] board, int i, int j) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
|| board[i][j] != 'E')
return;
board[i][j] = (char) ('0' + adjMineNum);
else {
board[i][j] = 'B';
updateOneSquare(board, i - 1, j - 1);
updateOneSquare(board, i - 1, j);
updateOneSquare(board, i - 1, j + 1);
updateOneSquare(board, i, j - 1);
updateOneSquare(board, i, j + 1);
updateOneSquare(board, i + 1, j - 1);
updateOneSquare(board, i + 1, j);
updateOneSquare(board, i + 1, j + 1);
}
}

public char[][] updateBoard(char[][] board, int[] click) {
int i = click[0], j = click[1];
if (board[i][j] == 'M')
board[i][j] = 'X';
else
updateOneSquare(board, i, j);
return board;
}
``````

···

• Great solution and explanation. Thanks.

• Python version:

``````class Solution(object):
def updateBoard(self, board, click):
"""
:type board: List[List[str]]
:type click: List[int]
:rtype: List[List[str]]
"""
m = len(board)
n = len(board[0])
row = click[0]
col = click[1]

if board[row][col] == 'M':
board[row][col] = 'X'
else:
count = 0
for i in xrange(-1, 2):
for j in xrange(-1, 2):
if i == 0 and j == 0:
continue
r = row + i
c = col + j
if r >= m or r < 0 or c >=n or c < 0:
continue
if board[r][c] == 'M' or board[r][c] == 'X':
count += 1
if count > 0:
board[row][col] = str(count)
else:
board[row][col] = 'B'
for i in xrange(-1, 2):
for j in xrange(-1, 2):
if i == 0 and j == 0:
continue
r = row + i
c = col + j
if r >= m or r < 0 or c >=n or c < 0:
continue
if board[r][c] == 'E':
self.updateBoard(board, [r, c])
return board

``````

• Are the time complexites of both DFS and BFS roughly `O(n)` where n is the number of total elements in the board matrix?

• @snapfinger In worst case, for example, we explore at [0,0], there is only one mine in [matrix.length - 1, matrix[0].length - 1], so every cell is going to be explored, then time complexity is O(n).

• Thanks for sharing, but I have one confusion why stop further DFS when a cell is not a 'B'. I know this can prevent exploring unintended cell. Is there any reason behind this?

• @panzw This is the rule of the game.

• My DFS version

``````class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
if (board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}
int mine = 0;
int startRow = click[0] - 1 < 0? 0: click[0] - 1;
int endRow = click[0] + 1 >= board.length? board.length - 1: click[0] + 1;
int startCol = click[1] - 1 < 0? 0: click[1] - 1;
int endCol = click[1] + 1 >= board[0].length? board[0].length - 1: click[1] + 1;
for (int i = startRow; i <= endRow; i++) {
for (int j = startCol; j <= endCol; j++) {
if (board[i][j] == 'M' || board[i][j] == 'X') {
mine++;
}
}
}
if (mine != 0) {
board[click[0]][click[1]] = (char)(mine + '0');
} else {
board[click[0]][click[1]] = 'B';
for (int i = startRow; i <= endRow; i++) {
for (int j = startCol; j <= endCol; j++) {
if (board[i][j] == 'E')
updateBoard(board, new int[]{i, j});
}
}
}
return board;
}
}
``````

• lol...I found that I just solve it 11 days ago. And today I solve it with a little different way

``````class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
if (board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}
dfs(board, click[0], click[1]);
return board;
}
public void dfs(char[][] board, int i, int j) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'E') {
return;
}
int mine = 0;
int startRow = i - 1 < 0? 0: i - 1;
int endRow = i + 1 >= board.length? board.length - 1: i + 1;
int startCol = j - 1 < 0? 0: j - 1;
int endCol = j + 1 >= board[0].length? board[0].length - 1: j + 1;
for (int m = startRow; m <= endRow; m++) {
for (int n = startCol; n <= endCol; n++) {
if (board[m][n] == 'M' || board[m][n] == 'X') {
mine++;
}
}
}
if (mine != 0) {
board[i][j] = (char)(mine + '0');
} else {
board[i][j] = 'B';
dfs(board, i + 1, j);
dfs(board, i - 1, j);
dfs(board, i, j + 1);
dfs(board, i, j - 1);
dfs(board, i + 1, j + 1);
dfs(board, i + 1, j - 1);
dfs(board, i - 1, j - 1);
dfs(board, i - 1, j + 1);
}
}
}
``````

• is the time complexity O(m*n)?

• @shawngao I think i use the similar idea but failed. Can you help me check what's wrong in my C++ code?

//Code
class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
if (board.size() == 0 || board[0].size() == 0) return board;
int row = board.size(), col = board[0].size();
if (board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}

``````    //BFS
bfs(board, click[0], click[1], row, col);
return board;
}

void bfs(vector<vector<char>>& board, int i, int j, int row, int col) {
queue<pair<int, int>> q;
q.push(make_pair(i, j));
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
int neighMint = adjMine(board, x, y, row, col);
if (neighMint == 0) {
board[x][y] = 'B';
for (int i = x - 1; i <= x + 1; i ++) {
for (int j = y - 1; j <= y + 1; j++) {
if (i == x && j == y) continue;
if (0 <= i && i < row && 0 <= j && j <= col && board[i][j] == 'E') q.push(make_pair(i, j));
}
}
}
else {
board[x][y] = neighMint + '0';
}
q.pop();
}
}

int adjMine(vector<vector<char>>& board, int x, int y, int row, int col) {
int count = 0;
for (int i = x - 1; i <= x + 1; i ++) {
for (int j = y - 1; j <= y + 1; j++) {
if (0 <= i && i < row && 0 <= j && j <= col && board[i][j] == 'M') count++;
}
}
return count;
}
``````

};

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