给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X

运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

Solution

回溯算法入门级详解

参考 @liuyubobobo 、@zzyuting

• floodfill

• 利用深度优先搜索

• 首先检查边界，如果元素为 O，将其 和与其相连 的 O 都替换为 1

• 然后遍历，将剩余的所有 O替换为 X

• 最后将 1 替换为 O

// @lc code=start
class Solution {
private:
    int m, n;

    bool inArea(int x, int y){
        return x>=0 && x<m && y>=0 && y<n;
    }

    void dfs(vector<vector<char>>& board, int x, int y){
        if(inArea(x,y) && board[x][y]=='O'){
            board[x][y]='1';
            dfs(board, x-1, y);
            dfs(board, x+1, y);
            dfs(board, x, y-1);
            dfs(board, x, y+1);
        }
        return;
    }

public:
    void solve(vector<vector<char>>& board) {
        m = board.size();
        if(m==0) return;
        n = board[0].size();
        if(n==0) return;

        for(int i=0; i<m; ++i){
            dfs(board,i,0);
            dfs(board,i, n-1);
        }

        for(int j=0; j<n; ++j){
            dfs(board, 0, j);
            dfs(board, m-1, j);
        }

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(board[i][j]=='1'){
                    board[i][j]='O';
                } else {
                    board[i][j]='X';
                }
            }
        }
    }
};
// @lc code=end