首页分享【力扣日记】994 腐烂的橘子

【力扣日记】994 腐烂的橘子

来源：花匠小妙招时间：2024-12-29 17:12

题目描述

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

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

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

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

算法思路

本来是想遍历，但是当grid[i][j]==2时对四周进行感染，之后没办法分辨其他的烂橘子是这一轮本来存在的还是这一轮感染的。

解决方法是第一次遍历时标记出所有烂橘子的位置，然后再进行迭代，每一轮搜索的起始点都保存在存放烂橘子坐标的容器里。

广度优先搜索BFS：

class Solution: def orangesRotting(self, grid: List[List[int]]) -> int:if len(grid)==0:return -1 m,n=len(grid),len(grid[0]) visit=[[False]*n for i in range(m)] # direction=[[-1,0],[0,1],[1,0],[0,-1]] # row,col # 第一次遍历，保存所有烂橘子的坐标 stack=[] for i in range(m): for j in range(n): if grid[i][j]==2: stack.append([i,j]) #得到烂橘子坐标后迭代感染，每次新感染的橘子坐标放入stack_next，res是总计感染时间 res=0 while True: stack_next=[] while stack: i,j=stack.pop() # direction的坐标偏移配合for循环很好的完成了四次感染，代码复用 for d in direction: i_new,j_new=i+d[0],j+d[1] if 0<=i_new<m and 0<=j_new<n and visit[i_new][j_new]==False and grid[i_new][j_new]==1: visit[i_new][j_new]=True grid[i_new][j_new]=2 stack_next.append([i_new,j_new]) #如果不存在新感染的橘子就可以退出循环，否则感染时间+1 if len(stack_next)==0: break res+=1 stack=list(stack_next) # 最后遍历一次网格，如果还有未感染的橘子，则返回-1 for i in range(m): for j in range(n): if grid[i][j]==1: return -1 return res

123456789101112131415161718192021222324252627282930313233343536

执行用时 :48 ms, 在所有 Python3 提交中击败了94.61%的用户
内存消耗 :13.5 MB, 在所有 Python3 提交中击败了17.24%的用户

试图优化

class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: m,n=len(grid),len(grid[0]) direction=[[-1,0],[0,1],[1,0],[0,-1]] # row,col # 第一次遍历，保存所有烂橘子的坐标，检查是否存在新鲜橘子,并给橘子计数 stack,xianjuzi,xjz_n=[],True,0 for i in range(m): for j in range(n):if grid[i][j]==1:xianjuzi,xjz_n=False,xjz_n+1if grid[i][j]==2: stack.append([i,j])# 如果没有新鲜橘子返回0，没有烂橘子返回-1 if xianjuzi:return 0 if not stack:return -1 #得到烂橘子坐标后迭代感染，每次新感染的橘子坐标放入stack_next，res是总计感染时间 res=0 while True: stack_next=[] while stack: i,j=stack.pop() # direction的坐标偏移配合for循环很好的完成了四次感染，代码复用 for d in direction: i_new,j_new=i+d[0],j+d[1] if 0<=i_new<m and 0<=j_new<n and grid[i_new][j_new]==1:#每感染一个橘子，xjz_n-1xjz_n-=1grid[i_new][j_new]=2stack_next.append([i_new,j_new]) #如果不存在新感染的橘子就可以退出循环，否则感染时间+1 if len(stack_next)==0: break res+=1 stack=list(stack_next) # 那么最后不用再遍历一次网格，仅判断是否还有新鲜橘子存在即可。 if xjz_n:return -1 return res

12345678910111213141516171819202122232425262728293031323334353637

但是时间并不理想。不确定到底是结构上的优化不明显还是说样本太小。

执行用时 :52 ms, 在所有 Python3 提交中击败了87.72%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了17.24%的用户