BFS Solution +1s


  • 1
    C

    BFS solution solve this problem, firstly create the queue and put the 'O' into the queue in the border layer, if the border layer is 'O' start to bfs from this position, if we can find the 'O' in the next layer or next... layer, it means this 'O' is not surrounded by 'X', change this 'O' to ''* or another character. and then for loop the board and change the 'O' to 'X', it means we can not reach it from the board 'O', and then change the '' to 'O'*

    public class Solution {
        public void solve(char[][] board) {
            
            if(board==null||board.length==0||board[0].length==0) return;
            
            int m = board.length;
            int n = board[0].length;
            
            Queue<int[]> queue = new LinkedList<int[]>();
            
            for(int i=0;i<m;i++){
                if(board[i][0]=='O')
                queue.offer(new int[]{i,0});
                if(board[i][n-1]=='O')
                queue.offer(new int[]{i,n-1});
            }
            for(int j=0;j<n;j++){
                if(board[0][j]=='O')
                queue.offer(new int[]{0,j});
                if(board[m-1][j]=='O')
                queue.offer(new int[]{m-1,j});
            }
            int[] dx = {-1,1,0,0};
            int[] dy = {0,0,-1,1};
            while(!queue.isEmpty()){
                int[] ele = queue.poll();
                board[ele[0]][ele[1]] = '*';
                for(int i=0;i<4;i++){
                    int x = ele[0] + dx[i];
                    int y = ele[1] + dy[i];
                    // except the 
                    if(1<=x&&x<m-1&&1<=y&&y<n-1&&board[x][y]=='O'){
                        queue.offer(new int[]{x,y});
                    }
                }
            }    
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(board[i][j]=='O'){
                        board[i][j] = 'X';
                    }
                    if(board[i][j]=='*'){
                        board[i][j] = 'O';
                    }
                }
            } 
        }
    }
    

Log in to reply
 

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