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

#include <iterator>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return char字符型vector<vector<>>
     */

    vector<pair<int,int>> v = {{-1,0},{1,0},{0,-1},{0,1}};

    void dfs(vector<vector<char>> board, int i, int j,vector<vector<bool>>& flag)
    {
        int m = board.size();
        int n = board[0].size();
        // 越界
        if(i<0||i>=m||j<0||j>=n)
            return;

        if(i>=0&&i<m&&j>=0&&j<n && board[i][j]=='B')
        {
            // 将当前位置的字符变为'A'
            board[i][j] = 'A';
            flag[i][j] = true;
        }
        
        // 遍历当前位置的四个方向
        for(auto [t_1,t_2]:v)
        {
            int t_i = i+t_1;
            int t_j = j+t_2;

            if(t_i>=0&&t_i<m&&t_j>=0&&t_j<n && board[t_i][t_j]=='B')
                dfs(board, t_i, t_j, flag);
        }

        return;
    }

    vector<vector<char> > solve(vector<vector<char> >& board) {
        // write code here

        int m = board.size();
        int n = board[0].size();
        
        // 对每个位置进行判断
        vector<vector<bool>> flag(m,vector<bool>(n,false));

        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                // 题目中其实已经给出思路。我们可以遍历边界，当遇到B字符时，就是递归的入口。递归时就找到与之相邻的没有被访问过的B字符位置即可
                if((i==0 || i==m-1 || j==0 || j==n-1) && board[i][j]=='B')
                {
                    // 递归，标记这部分区域
                    dfs(board,i,j,flag);
                }
            }
        }

        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                // 题目中其实已经给出思路。我们可以遍历边界，当遇到B字符时，就是递归的入口。递归时就找到与之相邻的没有被访问过的B字符位置即可
                if(i>0&&i<m-1&&j>0&&j<n-1 && board[i][j]=='B' && !flag[i][j])
                {
                    board[i][j] = 'A';
                }
            }
        }

        return board;
    }
};