题解 | #疯牛病II#

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

1. 统计初始情况下健康牛和患病牛的数量，并将患病牛的坐标加入到一个队列中。如果初始情况下就没有健康牛，则直接返回0。否则，我们使用一个循环模拟疯牛病传播的过程，直到所有健康牛都被感染为止。在每一轮模拟中，我们遍历队列中的所有患病牛，将周围4个方向上的健康牛变为患病牛，并将其坐标加入到新的队列中。然后，我们更新队列和已经过的分钟数，继续下一轮模拟。如果最终还有健康牛剩余，则说明无法全部被感染，此时我们返回-1；否则，我们返回已经过的分钟数

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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pasture int整型二维数组
# @return int整型
#
class Solution:
    def healthyCowsII(self, pasture: List[List[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))
        if healthy == 0:
            return 0

        minutes = 0  
        while queue and healthy > 0:
            new_queue = []  
            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  
            minutes += 1 

        if healthy > 0: 
            return -1
        else:
            return minutes