题解 | #疯牛病II#
疯牛病II
https://www.nowcoder.com/practice/2d5c96e452a949e09d98bb32aec3b61d
- 题目考察的知识点 : 递归,广度优先搜索
- 题目解答方法的文字分析:
- 统计初始情况下健康牛和患病牛的数量,并将患病牛的坐标加入到一个队列中。如果初始情况下就没有健康牛,则直接返回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
牛客高频top202题解系列 文章被收录于专栏
记录刷牛客高频202题的解法思路