130. Surrounded Regions

The basic idea is excluding any O that can be reached from O on the border by dfs:

1. Using a two dimension array isBorder to record all such regions during traversal
2. For any board[i][j], if isBorder[i][j] is false, flip board[i][j] to X.

int array[][] = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

public void solve(char[][] board) {
    if( board.length < 1 || board[0].length < 1 )
        return;
    boolean isBorder[][] = new boolean[board.length][board[0].length]; // record the result of dfs
	
    // 1. dfs 'O' on the border
    for(int i = 0; i < board.length; i++) {
        if( board[i][0] == 'O' && !isBorder[i][0] )
            traverse(board, isBorder, i, 0);
        if( board[i][board[0].length - 1] == 'O' && !isBorder[i][board[0].length - 1] )
            traverse(board, isBorder, i, board[0].length - 1);
    }
    for(int i = 0; i < board[0].length; i++) {
        if( board[0][i] == 'O' && !isBorder[0][i] )
            traverse(board, isBorder, 0, i);
        if( board[board.length - 1][i] == 'O' && !isBorder[board.length - 1][i] )
            traverse(board, isBorder, board.length - 1, i);
    }
	
    // 2. Flip regions
    for(int i = 0; i < board.length; i++)
        for(int j = 0; j < board[0].length; j++)
            if( !isBorder[i][j] )
                board[i][j] = 'X';
}

public void traverse(char[][] board, boolean[][] isBorder, int r, int c) {
    isBorder[r][c] = true;
    for(int i = 0; i < 4; i++) {
        int rr = r + array[i][0];
        int cc = c + array[i][1];
        if( rr >= 0 && cc >= 0 && rr < board.length && cc < board[0].length 
           && board[rr][cc] == 'O' && !isBorder[rr][cc] )
            traverse(board, isBorder, rr, cc);
    }
}