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

知识点

flood fill

思路

我们考虑什么B字符不能转化为A；我们从边缘的B的位置开始flood fill 访问到的位置说明不是被A包围的B

则不能变为A，我们将剩余的B都转化为A即可。

时间复杂度

每个点最多访问一次，时间复杂度为

AC code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return char字符型vector<vector<>>
     */
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, -1, 0, 1};
    vector<vector<char> > solve(vector<vector<char> >& board) {
        int n = board.size(), m = board[0].size();
        vector<vector<bool>> st(n, vector<bool>(m, false));
        function<void(int, int)> dfs = [&](int x, int y) {
            for (int i = 0; i < 4; i ++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 and nx < n and ny >= 0 and ny < m and !st[nx][ny] and board[nx][ny] == 'B') {
                    st[nx][ny] = true;
                    dfs(nx, ny);
                }
            }
        };
        for (int i = 0; i < n; i ++) {
            if (!st[i][0] and board[i][0] == 'B') {
                st[i][0] = true;
                dfs(i, 0);
            }
            if (!st[i][m - 1] and board[i][m - 1] == 'B') {
                st[i][m - 1] = true;
                dfs(i, m - 1);
            }
        }
        for (int i = 0; i < m; i ++) {
            if (!st[0][i] and board[0][i] == 'B') {
                st[0][i] = true;
                dfs(0, i);
            }
            if (!st[n - 1][i] and board[n - 1][i] == 'B') {
                st[n - 1][i] = true;
                dfs(n - 1, i);
            }
        }

        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (board[i][j] == 'A') continue;
                if (!st[i][j]) board[i][j] = 'A';
            }
        }
        return board;
    }
};