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:
Beginning from 'O' in the edge, find all 'O' linked with it. Set all these 'O' to be 't', these 'O's are not surrounded by 'X'

Then set all other 'O' to be 'X' and set 't' back to 'O'.

Complexity is O(mn)


import java.util.*;

class Pair{
    int x;
    int y;
    Pair(int x, int y){this.x = x; this.y = y;}
}


public class Solution {
   
   
    public void solve(char[][] board) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(board == null) return;
       
        int n = board.length;
        if(n == 0) return;
        int m = board[0].length;
        if(m==0) return;

        LinkedList<Pair> buf = new LinkedList<Pair>();
        for(int i = 0; i < n; i++){
            if(board[i][0] == 'O') {
                board[i][0] = 't';
                buf.add(new Pair(i,0));
            }
            if(board[i][m-1] == 'O'){
                board[i][m-1] = 't';
                buf.add(new Pair(i, m -1));
            }
               
        }
        for(int i = 0; i < m ; i++){
            if(board[0][i] == 'O'){
         board[0][i] = 't';
                buf.add(new Pair(0,i));
         }

         if(board[n-1][i] == 'O'){
         board[n-1][i] = 't';
         buf.add(new Pair(n-1,i));
         }
        }
       
        while(!buf.isEmpty()){
            Pair node = buf.removeFirst();
            int x = node.x;
            int y = node.y;
            if(x-1 >= 0 && board[x-1][y] == 'O'){
                board[x-1][y] = 't';
                buf.add(new Pair(x-1,y));
            }
            if(x+1 < n && board[x+1][y] == 'O'){
                board[x+1][y] = 't';
                buf.add(new Pair(x+1,y));
            }
           
            if(y-1 >= 0 && board[x][y-1] == 'O'){
                board[x][y-1] = 't';
                buf.add(new Pair(x,y-1));
            }
           
            if(y+1 < m && board[x][y+1] == 'O'){
                board[x][y+1] = 't';
                buf.add(new Pair(x,y+1));
            }
        }
       
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                else if(board[i][j] == 't') board[i][j] = 'O';
            }
        }
       
    }
}