本文主要是介绍【hot100篇-python刷题记录】【腐烂的橘子】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
R6-图论
思路：尽可能从中间开始吧，向四周扩散。
实际上就可以理解为BFS搜索。
使用rot,fresh集合分别记录腐烂、新鲜的集合的元素下标
使用集合是为了更方便增减元素(直接使用-=即可，集合加减）
遍历，rot集合中的每一个元素，对其进行上下左右移动，判断是否存在
存在的话就fresh-rot集合得到最后的集合。
class Solution:def orangesRotting(self, grid: List[List[int]]) -> int:m=len(grid)n=len(grid[0])rot={(i,j) for i in range(m) for j in range(n) if grid[i][j]==2}fresh={(i,j) for i in range(m) for j in range(n) if grid[i][j]==1}time=0while fresh:if not rot:return -1rot={(i+di,j+dj) for i,j in rot for di,dj in [(0,1),(0,-1),(1,0),(-1,0)] if (i+di,j+dj) in fresh}fresh-=rottime+=1return time
ps:
上下左右移动
# 设初始点为 (i, j)
for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]: # 上、下、左、右i + di, j + dj
这篇关于【hot100篇-python刷题记录】【腐烂的橘子】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
