Java solution using a queue


  • 0
    L

    This solution is slower as I could get this with 37%. Here is what it does:

       public void solve(char[][] board) {
         if(board.length==0) {
             return;
         }
         
         Queue<Pair> queue = new LinkedList<Pair>();
         for(int i=0;i<board.length;i++) {
             for(int j=0;j<board[i].length;j++) {
                 //Put all 'Os' at the boundary into the queue to run a
                 //BFS.
                 if(board[i][j]=='O' && ((i==0 || i==board.length-1) || 
                    (j==0 || j==board[i].length-1))) {
                    queue.add(new Pair(i,j));
                 }
             }
         }
         while(!queue.isEmpty()) {
            Pair p = queue.poll();
            board[p.x][p.y]='+';
            Pair temp;
            //Find all neighbours that are connected.
            if(p.x>0 && board[p.x-1][p.y]=='O') {
                //up.
                queue.add(new Pair(p.x-1,p.y));
            }
            if(p.x<board.length-1 && board[p.x+1][p.y]=='O') {
                //down.
                queue.add(new Pair(p.x+1,p.y));
            }
            if(p.y>0 && board[p.x][p.y-1]=='O') {
                //left.
                queue.add(new Pair(p.x,p.y-1));
            }
            if(p.y<board[0].length-1 && board[p.x][p.y+1]=='O') {
                //left.
                queue.add(new Pair(p.x,p.y+1));
            }        
         }
         
         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';
                 }
                 if(board[i][j]=='+') {
                     board[i][j]='O';
                 }
             }
         }
        }
        
        private class Pair {
            int x;
            int y;
            Pair(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
    

Log in to reply
 

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