Java Solution, DFS + BFS


  • 29

    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;
            Queue<int[]> queue = new LinkedList<>();
            queue.add(click);
            
            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') {
                                    queue.add(new int[] {r, c});
                                    board[r][c] = 'B'; // Avoid to be added again.
                                }
                            }
                        }
                    }
                }
            }
            
            return board;
        }
    }
    

  • 0

    Great Solution! Thanks!


  • 2
    J

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


  • 0

    @jordandong Yes. Updated my post.


  • 0
    R

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


  • 2

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


  • 3

    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;
        }
    

  • 1

    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; 
            Queue<int[]> q1 = new LinkedList<>();
            Queue<int[]> q2 = new LinkedList<>();
            
            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';
                            q1.addAll(q2);
                        } else board[X][Y] = Character.forDigit(cnt, 10);
                        break;
                }
            }
            return board;

  • 1
    B

    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;
        int adjMineNum = findAdjMineNum(board, i, j);
        if (adjMineNum > 0)
            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;
    }
    

    ···


  • 0
    Y

    Great solution and explanation. Thanks.


  • 0
    R

    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
            
    

  • 0

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


  • 0
    W

    @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).


  • 0
    P

    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?


Log in to reply
 

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