【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