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

给定一个二维数组，数组由两个元素‘O'和’X'组成，找到所有被X包围的O, 将O变为X。我们可以从数组的四个边开始，如果遇到‘O'就从当前点就行深搜，并且将所有连通的O进行标记，这些点都不是被X包围的。我们遍历完四个边上的点之后，剩下的没有被标记的O都是被X包围的，它们需要变为X。接下来我们仅需要遍历一遍数组，标记过的O保持不变，没标记过的变为X。在深搜的时候，如果数组中有很多O,这是可能会产生堆栈溢出，我们可以先判断再压栈，将深搜进行优化，防止溢出。代码如下：

public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; i++) {
            if(board[i][0] == 'O') 
                getZero(i, 0, board);
        }
        for(int i = 0; i < n; i++) {
            if(board[0][i] == 'O') 
                getZero(0, i, board);
        }
        for(int i = 1; i < n; i++) {
            if(board[m - 1][i] == 'O')
                getZero(m - 1, i, board);
        }
        for(int i = 1; i < m; i++) {
            if(board[i][n - 1] == 'O')
                getZero(i, n - 1, board);
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 'Y') {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }
    
    public void getZero(int i, int j, char[][] board) {
        board[i][j] = 'Y';
        if(i - 1 > 0 && board[i - 1][j] == 'O') getZero(i - 1, j, board);
        if(i + 1 < board.length && board[i + 1][j] == 'O') getZero(i + 1, j, board);
        if(j - 1 > 0 && board[i][j - 1] == 'O') getZero(i, j - 1, board);
        if(j + 1 < board[0].length && board[i][j + 1] == 'O') getZero(i, j + 1, board);
        return;
    }
}