[数据结构与算法]Leetcode 130 被围绕的区域

题目描述：

给你一个?m x n?的矩阵?board?，由若干字符?'X'?和?'O'?，找到所有被?'X'?围绕的区域，并将这些区域里所有的?'O'?用?'X'?填充。

示例：

输入：board?=?[["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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

思路：

这个题关键是要识别 被‘X’围绕的‘O’ 和 未被‘X’围绕的‘O’。

因为?任何边界上的?'O'?都不会被填充为?'X' ，所以 边界和与边界相连的‘O’ 都不会被置为‘X’。

因此，我们只需要从边界开始寻找相邻的‘O’，然后把这部分‘O’标记。

最后把未标记的‘O’置为‘X’，把标记的‘O’保留即可。

代码：

class Solution {
public:

    void dfs(int x, int y, int len, int col, vector<vector<char>>& board){
        if (x<0||x>len||y<0||y>col||board[x][y]!='O') return;
        board[x][y] = 'A';
        dfs(x-1,y,len,col,board);
        dfs(x+1,y,len,col,board);
        dfs(x,y-1,len,col,board);
        dfs(x,y+1,len,col,board);
    }

    void solve(vector<vector<char>>& board) {
        int len = board.size()-1;
        int col = board[0].size()-1;
        for (int i=0; i<=len; ++i){
            dfs(i,0,len,col,board);
            dfs(i,col,len,col,board);
        }
        for (int i=0; i<=col; ++i){
            dfs(0,i,len,col,board);
            dfs(len,i,len,col,board);
        }
        for (int i=0; i<=len; ++i)
            for (int j=0; j<=col; ++j)
                if (board[i][j]=='O') board[i][j]='X';
                else if (board[i][j]=='A') board[i][j]='O';
    }
};