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

Core idea: start from the O on the board line, use BFS/DFS search, if find O then replace with #, otherwise return. After the flood fill, replace # with O, and the remaining O with X (which means O on the border line can not connect with the inner O);

public static class Pair {
        int x;
        int y;

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

    public void solve(char[][] board) {  
        if (board == null || board.length <= 0) {  
            return;  
        }  

        int m = board.length;  
        int n = board[0].length;  

        Queue<Pair> queue = new LinkedList<Pair>();  


        for (int i = 0; i < m; i++) { 
            //first line;
            if (board[i][0] == 'O') {  
                queue.add(new Pair(i,0));  
                bfs(queue, board);  
            }  
            //last line;
            if (board[i][n - 1] == 'O') {  
                queue.add(new Pair(i,n-1));  
                bfs(queue, board);  
            }  
        }  
        for (int j = 1; j < n - 1; j++) {
            //first column
            if (board[0][j] == 'O') {  
                queue.add(new Pair(0,j));  
                bfs(queue, board);  
            }  
            //last column
            if (board[m - 1][j] == 'O') {  
                queue.add(new Pair(m-1,j));  
                bfs(queue, board);  
            }  
        }  

        //replace with X if still O
        for (int i = 0; i < m; i++) {  
            for (int j = 0; j < n; j++) {  
                if (board[i][j] == 'O') {  
                    board[i][j] = 'X';  
                } else if (board[i][j] == '#') {  
                    board[i][j] = 'O';  
                }  
            }  
        }  
    }  

    private void bfs(Queue<Pair> queue, char[][] board) {  
        int m = board.length;
        int n = board[0].length;
        while (!queue.isEmpty()) {  
            Pair p = queue.poll();  
            int i = p.x;
            int j = p.y;
            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 'X') {  
                continue;  
            }  
            board[i][j] = '#';  
            queue.add(new Pair(i+1, j));  
            queue.add(new Pair(i, j+1));  
            queue.add(new Pair(i, j-1));  
            queue.add(new Pair(i-1, j));  
        }  
    }