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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题考察深度优先搜索（DFS）算法，用于遍历和标记被 'A' 围绕的区域。

题目解答方法的文字分析

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

我们可以使用DFS来解决这个问题：

1. 从矩阵的边界上的每一个 'B' 开始，进行DFS搜索，标记与其相连的所有 'B' 为特殊标记，如 '#'.
2. 遍历整个矩阵，将剩余的 'B' 变为 'A'，将特殊标记的 '#' 恢复为 'B'。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<char>> solve(vector<vector<char>>& board) {
        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 - 1; 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;
    }

    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);
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！