LeetCode刷题笔记——994. 腐烂的橘子

qhdlgd17857 11 0 PDF 2020-12-22 21:12:53

难度:简单 一、题目描述: 二、解题分析: 1、解析 观察到对于所有的腐烂橘子,其实它们在广度优先搜索上是等价于同一层的节点的。 假设这些腐烂橘子刚开始是新鲜的,而有一个腐烂橘子(我们令其为超级源点)会在下一秒把这些橘子都变腐烂,而这个腐烂橘子刚开始在的时间是 -1 ,那么按照广度优先搜索的算法,下一分钟也就是第 0分钟的时候,这个腐烂橘子会把它们都变成腐烂橘子,然后继续向外拓展,所以其实这些腐烂橘子是同一层的节点。那么在广度优先搜索的时候,我们将这些腐烂橘子都放进队列里进行广度优先搜索即可,最后每个新鲜橘子被腐烂的最短时间其实是以这个超级源点的腐烂橘子为起点的广度优先搜索得到的结果

用户评论
请输入评论内容
评分:
暂无评论