题解 | #疯牛病II#

疯牛病II

https://www.nowcoder.com/practice/2d5c96e452a949e09d98bb32aec3b61d

  • 题目考察的知识点 : 递归,广度优先搜索
  • 题目解答方法的文字分析:
  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
牛客高频top202题解系列 文章被收录于专栏

记录刷牛客高频202题的解法思路

全部评论

相关推荐

12-02 16:21
中南大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务