130. Surrounded Regions

Given a 2D board containing'X'and'O'(theletterO), 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

Analysis:

if a 'O' is not captured, it must has a connection path to a 'O' on the edge.

So we can iterate through all O on the edge, starting from each O, we do BFS and mark all these connected O as Y.

When finished, we turn all O into X since they are not reachable during BFS, they must be those are captured. Then we turn Y into O. and we are done.

Be aware of BFS process, we need to check boundary when traversing, also we need to maintain a visited[][], a trick is to just mark visted as V, and only enqueue those are still O and reachable.

Code:

public class Solution {
    private int ROW = 0;
    private int COL = 0;
    private int[] xdir = {-1 ,1, 0 ,0};
    private int[] ydir = {0 ,0, -1, 1};
    public void solve(char[][] board) {
        if(board == null || board.length == 0)
        {
            return;
        }
        ROW = board.length;
        COL = board[0].length;
        for(int i=0; i<ROW; i++)
        {
            if(board[i][0] == 'O')
            {
                bfs(i, 0, board);
            }
            if(board[i][COL-1] == 'O')
            {
                bfs(i, COL-1, board);
            }
        }

        for(int i=0; i<COL; i++)
        {
            if(board[0][i] == 'O')
            {
                bfs(0, i, board);
            }
            if(board[ROW-1][i] == 'O')
            {
                bfs(ROW-1, i, board);
            }
        }

        for(int i=0; i<ROW; i++)
        {
            for(int j=0; j<COL; j++)
            {
                if(board[i][j] == 'Y')
                {
                    board[i][j] = 'O';
                }
                else if(board[i][j] == 'O')
                {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void bfs(int i, int j, char[][] board)
    {
        Deque<Integer> queue = new LinkedList<Integer>();
        queue.offer(i*COL + j);
        while(!queue.isEmpty())
        {
            Integer cur = queue.poll();
            int x = cur/COL;
            int y = cur%COL;
            board[x][y] = 'Y';
            for(int k=0; k<4; k++)
            {
                int xx = x + xdir[k];
                int yy = y + ydir[k];
                if(xx >= 0 && xx < ROW && yy >= 0 && yy < COL && board[xx][yy] == 'O')
                {
                    board[xx][yy] = 'V';
                    queue.offer(xx*COL + yy);
                }
            }
        }
    }
}