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

• 题目考察的知识点 : 宽度优先搜索
• 题目解答方法的文字分析：

1. 宽度优先搜索（BFS）遍历整个矩阵。我们首先将矩阵中与边界相邻的'B'入队，并将flag标记为已访问。然后，对队列中的元素进行BFS遍历，并将flag标记为已访问。最后，将未被标记过的'B'替换为'A'。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param board char字符型二维数组
# @return char字符型二维数组
#
class Solution:
    def solve(self, board: List[List[str]]) -> List[List[str]]:
        m, n = len(board), len(board[0])
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        flag = [[False] * n for _ in range(m)]
        queue = []
        # 将矩阵中与边界相邻的'B'入队，并将flag标记为已访问
        for i in range(m):
            if board[i][0] == "B":
                queue.append((i, 0))
            if board[i][n - 1] == "B":
                queue.append((i, n - 1))
        for i in range(n):
            if board[0][i] == "B":
                queue.append((0, i))
            if board[m - 1][i] == "B":
                queue.append((m - 1, i))
        # 对队列中的元素进行BFS遍历，并将flag标记为已访问
        while queue:
            x, y = queue.pop(0)
            flag[x][y] = True
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if (
                    0 <= nx < m
                    and 0 <= ny < n
                    and not flag[nx][ny]
                    and board[nx][ny] == "B"
                ):
                    queue.append((nx, ny))
        # 将未被标记过的'B'替换为'A'
        for i in range(m):
            for j in range(n):
                if not flag[i][j] and board[i][j] == "B":
                    board[i][j] = "A"
        return board