java BFS solution with explaination


  • 0

    The most important thing to solve is dealing with the empty block when there are no mines adjacent. Because there is a concept "adjacent", so BFS comes into my mind.
    hope it helps~

    public class Solution {
        int[][] dirs = {{0,-1}, {-1,-1}, {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}};
        public char[][] updateBoard(char[][] board, int[] click) {
            if(board == null || board[0].length == 0) {
                return board;
            }
            int x = click[0];
            int y = click[1];
            char c = board[x][y];
            switch(c) {
                case 'M':
                    board[x][y] = 'X';
                    break;
                    
                case 'E':
                    clickhelper(board, click);
                    break;
            }
            return board;
        }
        
        protected void clickhelper(char[][] board, int[] click) {
            int num = countadjacent(board, click[0], click[1]);
            int n = board[0].length;
            int x = click[0];
            int y = click[1];
            if(num > 0) {
                board[x][y] = (char)('0' + num);
            }else if(num == 0){
                LinkedList<Integer> queue = new LinkedList<Integer>();
                board[x][y] = 'B';
                queue.offer(x * n + y);
                while(!queue.isEmpty()) {
                    int code = queue.poll();
                    int tempx = code / n;
                    int tempy = code % n;
                    for(int[] dir : dirs) {
                        int count = countadjacent(board, tempx+dir[0], tempy+dir[1]);
                        if(count == 0) {
                            board[tempx+dir[0]][tempy+dir[1]] = 'B';
                            queue.offer((tempx+dir[0]) * n + (tempy+dir[1]));
                        }else if(count > 0) {
                            board[tempx+dir[0]][tempy+dir[1]] = (char)('0' + count);
                        }
                    }
                }
            }
        }
        
        protected int countadjacent(char[][] board, int x, int y) {
            if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
                return -1;
            }
            if(board[x][y] != 'E' && board[x][y] != 'M') {
                return -1;
            }
            int res = 0;
            for(int[] dir : dirs) {
                if(x+dir[0] >= 0 && x+dir[0] < board.length && y+dir[1] >= 0 && y+dir[1] < board[0].length) {
                    if(board[x+dir[0]][y+dir[1]] == 'M') {
                        res++;
                    }
                }   
            }
            return res;
        }
    }

Log in to reply
 

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