LC542
01 矩阵
图 BFS · 01 矩阵可视化:图与网格mat 到最近 0 的距离矩阵。
时间 O(n)空间 O(1)
题目1 / 7
题目与输入建立输入、目标与算法心智
沉岛:把访问过的陆地标记为 0
正在加载算法场景...
当前发生了什么
mat 到最近 0 的距离矩阵。
机器状态
队列、距离矩阵。
为什么正确
多源 BFS:所有 0 入队同时扩散,第一次到达即最短距。
不变量
多源 BFS 一次完成。
面试怎么说
0 全入队 BFS O(mn)。
人类输入
mat 到最近 0 的距离矩阵。
机制
多源 BFS:所有 0 入队同时扩散,第一次到达即最短距。
机器状态
队列、距离矩阵。
可观察结果
各格到最近 0 距离。
不变量
- · 多源 BFS 一次完成。
常见误区
- · 逐格 BFS 会 TLE。
迁移练习
- · LC994 腐烂
- · LC1091 最短路径
面试怎么答
0 全入队 BFS O(mn)。