130. Surrounded Regions Leetcode Java

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Solution:

From the description of the problem, we know that if 'O' is surrounded by 'X' it will be flipped. The way a 'O' is not surrounded is that, there exist a path that lead this 'O' to the boundaries of the board. Eg. the only one placed on the bottom boundary is not surrounded by 'X'. 

Let's think it in the opposite way:

1. any 'O' on the boundary is not surrounded by 'X'. Let's call this 'O' BO;

2. all 'O's that are BO's neighbors are not surrounded by 'X', neighbors means left, right, bottom, up. 

3. all 'O' that can reached by BO are not surrounded by 'X'. Reached by BO means, there exist a path from BO to the 'O' and the path is consisted of only 'O's. 

Clearly, we can do DFS/BFS starting from all BOs and mark all the reachable 'O' as "Don't flip" and flip all other 'O's to 'X'

Tips: use '*' to mark the position as "Don't flip". Flip after search by flip 'O' to 'X' and restore '*' to 'O'.

  public void solve(char[][] board) {  
     if(board==null || board.length==0 || board[0].length==0) return;  
     for(int i=0;i<board.length;i++){  
       if (board[i][0]=='O') helper(board,i,0);  
       if (board[i][board[0].length-1]=='O') helper(board,i,board[0].length-1);  
     }  
     for(int j=0;j<board[0].length;j++){  
       if(board[0][j]=='O') helper(board,0,j);  
       if(board[board.length-1][j]=='O') helper(board,board.length-1,j);  
     }  
     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';  
       }  
     }  
   }  
   public void helper(char[][] board, int i, int j){  
      LinkedList<Integer> q=new LinkedList<Integer>();  
      int ind=i*board[0].length+j;  
      board[i][j]='*';  
      q.offer(ind);  
      while(!q.isEmpty()){  
        int temp=q.poll();  
        int row=temp/board[0].length;  
        int col=temp%board[0].length;  
        if(row-1>=0 && board[row-1][col]=='O') {  
          q.offer(temp-board[0].length);  
          board[row-1][col]='*';    
        }  
        if(row+1<board.length && board[row+1][col]=='O'){  
          q.offer(temp+board[0].length);  
          board[row+1][col]='*';  
        }  
        if(col-1>=0 && board[row][col-1]=='O'){  
          q.offer(temp-1);  
          board[row][col-1]='*';  
        }  
        if(col+1<board[0].length && board[row][col+1]=='O') {  
          q.offer(temp+1);  
          board[row][col+1]='*';  
      }  
   }  
  }