题解 | #疯牛病I#

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

1. 首先遍历整个牧场，记录初始情况下健康牛和患病牛的数量，并将患病牛的坐标加入到一个队列中。然后，我们重复执行以下步骤kk次，模拟kk分钟内疯牛病的传播过程：从队列中取出一个患病牛；将该患病牛周围4个方向上的健康牛变为患病牛，并将其坐标加入到新的队列中；
2. 重复执行，直到队列为空。
3. 在模拟完kk次疯牛病传播过程之后，我们统计牧场中剩余的健康牛数量并返回

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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pasture int整型二维数组
# @param k int整型
# @return int整型
#
class Solution:
    def healthyCows(self, pasture: List[List[int]], k: int) -> int:
        m, n = len(pasture), len(pasture[0])
        queue = []  # 定义用于存储患病牛的队列
        healthy = 0  # 记录当前健康牛的数量

        # 统计初始情况下健康牛和患病牛的数量，并将患病牛加入到队列中
        for i in range(m):
            for j in range(n):
                if pasture[i][j] == 1:
                    healthy += 1
                elif pasture[i][j] == 2:
                    queue.append((i, j))

        # 模拟疯牛病传播过程k次
        for t in range(k):
            new_queue = []  # 存储本轮被感染的牛的坐标

            # 遍历队列中所有患病牛，将周围4个方向上的健康牛变为患病牛并加入新的队列中
            for x, y in queue:
                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and pasture[nx][ny] == 1:
                        pasture[nx][ny] = 2
                        new_queue.append((nx, ny))
                        healthy -= 1  # 每感染一个健康牛，就将其从健康牛的数量中减去

            queue = new_queue  # 更新队列

        return healthy  # 返回最终健康牛的数量