题解 | #牛群的活动区域#

注意这道题这里的解题思路要从A上转到B中

题目中说的是 请你编写一个程序，找到所有被 'A' 围绕的区域，并将这些区域里所有的 'B' 用 'A' 填充 ，第一反应就是从A出发寻找可以围成一个圈的内容，然后将其中心位置填充。但是这里需要转换一下思路，想想我们不需要改变的那些B的特点：都与边界有联系，所以思路变为：

1. 从边缘寻找B，然后使用BFS，将和B相连接的所有B都转换为'#'占个位置
2. 将剩下的B都替换为A
3. 将 '#' 恢复

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return char字符型vector<vector<>>
     */
    
    void dfs(vector<vector<char>>&board,int i, int j){
        int m = board.size();
        int n = board[0].size();

        if(i<0 || i>=m || j<0 || j>=n || board[i][j] != 'B'){
            return;
        }
        board[i][j] = '#';

        // 递归进行DFS搜索
        dfs(board,i-1,j);
        dfs(board,i+1,j);
        dfs(board,i,j-1);
        dfs(board,i,j+1);
    }

    vector<vector<char> > solve(vector<vector<char> >& board) {
        // A表示有牛，B表示没
        // 找到A包围的区域，然后将内部的B用A填充
        // 转换为从边界的B开始扩展，标记相连的B为'#'
        // 遍历矩阵将剩余的B变为’A'
        if(board.empty() || board[0].empty()){
            return board;
        }

        int m = board.size();
        int n = board[0].size();

        // 对边界上的B进行DFS搜索，标记与其相连接的所有B
        for(int i=0;i<m;++i){
            // 第一列
            if(board[i][0] == 'B'){
                dfs(board,i,0);
            }
            // 最后一列
            if(board[i][n-1]=='B'){
                dfs(board,i,n-1);
            }
        }
        // 注意这里的第一个已经转换了
        for(int j=1;j<n;++j){
            // 第一行
            if(board[0][j] == 'B'){
                dfs(board,0,j);
            }
            // 最后一行
            if(board[m-1][j]=='B'){
                dfs(board,m-1,j);
            }
        }
        // 遍历矩阵将剩下的B变为A，同时恢复#为B
        for(int i=0;i<m;i++){
            for(int j=0;j<n;++j){
                if(board[i][j] == 'B'){
                    board[i][j] = 'A';
                }else if(board[i][j] == '#'){
                    board[i][j] = 'B';
                }
            }
        }
        return board;
    }
};