1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」——994. 腐烂的橘子

994. 腐烂的橘子

链接:https://leetcode-cn.com/problems/rotting-oranges/
难度:简单

题目

在给定的网格中,每个单元格可以有以下三个值之一:

值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。
每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1。

示例 1:

输入:[[2,1,1],[1,1,0],[0,1,1]]
输出:4
示例 2:

输入:[[2,1,1],[0,1,1],[1,0,1]]
输出:-1
解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。
示例 3:

输入:[[0,2]]
输出:0
解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。

提示:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] 仅为 0、1 或 2

思路

这道题,让人很容易想到的解决办法是BFS。如下图,我们可以把输入的网格想象成这样

开始我们初始化每个网格的访问状态,维护一个坏橘子列表,从坏橘子开始寻找四个方向是否有好橘子,四个方向上看完,有搜索到好橘子就感染成坏橘子,加入坏橘子列表。具体思路见代码注释。

方案代码

解法:

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # 网格的长,宽
        m, n = len(grid), len(grid[0])
        # 网格每一个坐标的访问状态
        visit = [[False] * n for y in range(m)]
        # 找出最开始时,网格中所有坏橘子的坐标
        stack = [[y,x] for y in range(m) for x in range(n) if grid[y][x]==2]
        # 坏橘子传染好橘子的四个方向,上下左右
        direction = [[-1,0], [1,0], [0,-1], [0,1]]
        # 初始时间
        minute = 0
        
        # 开始坏橘子传染好橘子的循环,直到没有好橘子可以被传染
        while True:
            # 初始化一个stack_next,把这一轮变坏的橘子装进里面
            stack_next = []
            # 开始对坏橘子进行审查,主要是看上下左右有没有好橘子
            while stack:
                # 拿出坏橘子的坐标点
                y, x = stack.pop()
                # 再看坏橘子上下左右的坐标对应的坐标
                for d in direction:
                    y_new, x_new = y + d[0], x + d[1]
                    # 如果坐标在网格范围内,而且坐标没有被访问过,且这个坐标确实有个好橘子
                    if -1 < y_new < m and -1 < x_new < n and not visit[y_new][x_new] and grid[y_new][x_new] == 1:
                        # 观察慰问一下这个好橘子,表示已经访问过了
                        visit[y_new][x_new] = True
                        # 告诉这个好橘子,你已被隔壁的坏橘子感染,现在你也是坏橘子了
                        grid[y_new][x_new] = 2
                        # 放进stack_next里面,集中管理,精准隔离,方便排查下一轮会变坏的橘子
                        stack_next.append([y_new, x_new])
            # 如果橘子们都检查完了发现再无其他坏橘子,终止循环,宣布疫情结束
            if not stack_next: break
            # 把这一轮感染的坏橘子放进stack里,因为我们每一轮都是从stack开始搜索的
            stack = stack_next
            # 看来橘子们还没凉透,来,给橘子们续一秒,哦不,续一分钟
            minute += 1
        
        # 经过传染,审查,隔离的循环后,如果还有好橘子幸存,返回-1宣布胜利,否则返回橘子们的存活时间
        return -1 if ['survive' for y in range(m) for x in range(n) if grid[y][x]==1] else minute


原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/uncategorized/174.html