Java BFS solution


  • 0
    M

    I tried dfs. But it throws stack overflow exception.

    public class Solution {
        private int M, N;
        private int[] xx = {-1, 1, 0, 0};
        private int[] yy = {0, 0, -1, 1};
        public void solve(char[][] board) {
            if(board == null || board.length==0) return;
            M = board.length;
            N = board[0].length;
            for(int i=0; i<M; i++){
                if(board[i][0]=='O'){
                    bfs(i, 0, board);
                }
            }
            for(int i=0; i<M; i++){
                if(board[i][N-1]=='O'){
                    bfs(i, N-1, board);
                }
            }
            for(int j=0; j<N; j++){
                if(board[0][j]=='O'){
                    bfs(0, j, board);
                }
            }
            for(int j=0; j<N; j++){
                if(board[M-1][j]=='O'){
                    bfs(M-1, j, board);
                }
            }
            for(int i=0; i<board.length; i++){
                for(int j=0; j<board[0].length; j++){
                    if(board[i][j] == 'O'){
                        board[i][j] = 'X';
                    } else if(board[i][j] == 'A'){
                        board[i][j] = 'O';
                    }
                }
            }
        }
        
        private void bfs(int x, int y, char[][] board){
            Queue<Node> que = new LinkedList<>();
            que.offer(new Node(x, y));
            board[x][y] = 'A';
            while(!que.isEmpty()){
                Node node = que.poll();
                for(int d=0; d<4; d++){
                    int i = node.x + xx[d];
                    int j = node.y + yy[d];
                    if(i>=0 && i<M && j>=0 && j<N && board[i][j]=='O'){
                        que.offer(new Node(i, j));
                        board[i][j] = 'A';
                    }
                }
            }
        }
        class Node{
            int x, y;
            Node(int x, int y){
                this.x = x;
                this.y = y;
            }
        }
        
        // stack overflow
        private void dfs(int x, int y, char[][] board){
            board[x][y] = 'A';
            for(int d=0; d<4; d++){
                int i = x+xx[d];
                int j = y+yy[d];
                if(i>=0 && i<M && j>=0 && j<N && board[i][j]=='O'){
                    dfs(i, j, board);
                }
            }
        }
    }
    

Log in to reply
 

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