My concise JAVA solution based on BFS


  • 0

    Explanation

    The basic idea is to find all O connecting to 4 borders, then flip the left O into X.

    For this problem, stack will overflow if we use DFS, because DFS method just pushes nodes to stack till meets the leaf, and then processes from the leaf backtracking to the root. If the path from root to leaf is too long, it will cause stack overflow. So I adopt BFS to solve this problem, as the following:

    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int n = board.length, m = board[0].length;
    
        for (int i = 0; i < n; i++) {
            check(board, i, 0);
            check(board, i, m - 1);         
        }
    
        for (int j = 0; j < m; j++) {
            check(board, 0, j);
            check(board, n - 1, j);         
        }
    
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'V' || board[i][j] == 'O') // V means visited
                     board[i][j] = 'X';
            }
        }
    
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '1') // 1 means O at the border
                    board[i][j] = 'O';
            }
        }
    }
    
    // BFS
    void check(char[][] vec,int i, int j){
        Queue<Point> queue = new LinkedList<Point>();
        queue.offer(new Point(i, j));
    
        do {
            Point point = queue.poll();
            int x = point.x, y = point.y;           
            if(vec[x][y]=='1' || vec[x][y]=='V') // 1 means O at the border; V means visited
                continue;       
    
            if(vec[x][y]=='O'){
                vec[x][y]='1';
                if(x - 1 >= 0)
                    queue.offer(new Point(x-1,y));
                if(y - 1 >= 0)
                    queue.offer(new Point(x,y-1));
                if(x + 1 < vec.length)
                    queue.offer(new Point(x+1,y));
                if(y + 1 < vec[0].length)
                    queue.offer(new Point(x,y+1));
            } else {
                vec[x][y]='V'; //Set visited  
            }
        } while (!queue.isEmpty());
    }

Log in to reply
 

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