Leetcode 130 Surrounded Regions

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 1: Use recursive DFS will get system stack overflow when board is huge. Use BFS and queue is better way.

 public class Solution {  
   public void solve(char[][] board) {  
     int m=board.length;  
     if (m==0) return;  
     int n=board[0].length;  
     Queue<List<Integer>> qu=new LinkedList<>();  
     for (int j=0; j<n; j++) {  
       if (board[0][j]=='O') {board[0][j]='T'; qu.offer(Arrays.asList(0,j));}  
       if (board[m-1][j]=='O') {board[m-1][j]='T'; qu.offer(Arrays.asList(m-1,j));}  
     }  
     for (int i=1; i<m-1; i++) {  
       if (board[i][0]=='O') {board[i][0]='T'; qu.offer(Arrays.asList(i,0));}  
       if (board[i][n-1]=='O') {board[i][n-1]='T'; qu.offer(Arrays.asList(i,n-1));}  
     }  
     while (!qu.isEmpty()) {  
       List<Integer> one=qu.poll();  
       int i=one.get(0), j=one.get(1);  
       check(board,i+1,j,m,n,qu);  
       check(board,i-1,j,m,n,qu);  
       check(board,i,j+1,m,n,qu);  
       check(board,i,j-1,m,n,qu);  
     }  
     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]=='T') board[i][j]='O';  
       }  
     }  
   }  
   private void check(char[][] board, int i, int j, int m, int n, Queue<List<Integer>> qu) {  
     if (i<0 || i>=m || j<0 || j>=n) return;  
     if (board[i][j]!='O') return;  
     board[i][j]='T';  
     qu.offer(Arrays.asList(i,j));  
   }  
 }