Leetcode 994.腐烂的橘子（Rotting Oranges）
Leetcode 994.腐烂的橘子
1 题目描述（Leetcode题目链接）
在给定的网格中，每个单元格可以有以下三个值之一：
- 值 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 。
2 题解
广度优先搜索，首先将所有烂橘子的位置记录下来，每次循环将这些烂橘子周围的橘子都变烂，将新烂掉的橘子的位置都记录下来，下次循环再从这些新橘子往外扩散，具体见代码注释。
class Solution:def orangesRotting(self, grid: List[List[int]]) -> int:m = len(grid)n = len(grid[0])direct = [[1,0], [-1,0], [0,1], [0,-1]] #扩散方向clevel = [] #clevel表示当前层次烂橘子的位置for i in range(m):for j in range(n):if grid[i][j] == 2:clevel.append([i, j]) #找到初始所有烂橘子的位置time = 0while clevel:next_level = [] #下一层烂橘子的位置for org in clevel:grid[org[0]][org[1]] = 0 #需要把当前层的烂橘子置为0，避免以后重复访问for d in direct:x, y = org[0] + d[0], org[1] + d[1]if x >= 0 and x < m and y >= 0 and y < n and grid[x][y] == 1:next_level.append([x,y]) #一旦找到一个新的橘子，就往下一层里面放grid[x][y] = 2 #别忘记把这个橘子变烂if next_level: time += 1 #如果下一层里面有橘子，那就时间加一clevel = next_level #下一层替换为当前层for i in range(m):for j in range(n):if grid[i][j] == 1:return -1return time
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！