LC994
腐烂的橘子
图 BFS · 腐烂橘子可视化:图与网格grid 新鲜橘子被相邻腐烂,求最少分钟。
时间 O(n)空间 O(1)
题目1 / 14
题目与输入建立输入、目标与算法心智
新鲜 6 个,腐烂源 1 个
正在加载算法场景...
当前发生了什么
grid 新鲜橘子被相邻腐烂,求最少分钟。
机器状态
队列、fresh 计数、minutes。
为什么正确
多源 BFS:初始所有 2 入队,层数即时间。
不变量
BFS 每一层代表过去一分钟的同时扩散。
面试怎么说
所有 rotten 多源 BFS,层数即分钟;检查 fresh 是否清零,O(mn)。
人类输入
grid 新鲜橘子被相邻腐烂,求最少分钟。
机制
多源 BFS:初始所有 2 入队,层数即时间。
机器状态
队列、fresh 计数、minutes。
可观察结果
所有新鲜橘子腐烂的最少分钟数。
不变量
- · BFS 每一层代表过去一分钟的同时扩散。
常见误区
- · 结束后仍有 fresh>0 应返回 -1。
迁移练习
- · LC542 01 矩阵
- · LC1091 最短路径
面试怎么答
所有 rotten 多源 BFS,层数即分钟;检查 fresh 是否清零,O(mn)。