LeetCode 130. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’  (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’ s into ‘X’ s in that surrounded region.

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

Explanation:

Surrounded regions shouldn’t be on the border, which means that any ‘O’  on the border of the board are not flipped to ‘X’. Any ‘O’  that is not on the border and it is not connected to an ‘O’  on the border will be flipped to ‘X’ . Two cells are connected if they are adjacent cells connected horizontally or vertically.

解析：给定的二维数组，每个元素是X或者O，将所有被X包围的O替换成X，边界不做处理。从矩阵的四周由外向内处理，遍历矩阵的四条边，如果有O，则用 DFS 遍历，将所有连着的O都变成另一个字符，比如 ‘1’，这样剩下的O都是被包围的，然后将这些O变成X，把‘1’变回O就行了。

代码如下：

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int i, j;
        int row = board.size();
        if(row == 0)
            return;
        int col = board[0].size();
        for(int i=0; i < row; i++)
        {
            check(board, i, 0, row, col);
            if(col > 1)
                check(board, i, col-1, row, col);
        }
        for(int j=0; j < col; j++)
        {
            check(board, 0, j, row, col);
            if(row > 1)
                check(board, row-1,j, row, col);
        }
        for(int i = 0; i < row; i++)
            for(int j =0; j < col; j++)
            {
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        for(int i =0; i < row; i++)
            for(int j =0; j < col; j++)
                if(board[i][j] == '1')
                    board[i][j] = 'O';
        
    }
    void check(vector<vector<char>>& board, int i, int j, int row, int col)
    {
        if(board[i][j] == 'O')
        {
            board[i][j] = '1';
            if(i > 1)
                check(board, i-1, j, row, col);
            if(i+1 < row)
                check(board, i+1, j, row, col);
            if(j > 1)
                check(board, i, j -1, row, col);
            if(j+1 < col)
                check(board, i, j+1, row, col);
        }
    }
};

参考：

https://www.cnblogs.com/grandyang/p/4555831.html