Java Solution, DFS + BFS


  • 31

    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!


  • 3
    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;

  • 2
    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
            
    

  • 1

    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?


  • 0
    D

    @panzw This is the rule of the game.


  • 0
    F

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

Log in to reply
 

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