LC1091
二进制矩阵中的最短路径
图 BFS · 八方向可视化:图与网格n×n 二进制矩阵 0→1 最短路径(八方向)。
时间 O(n)空间 O(1)
题目1 / 9
题目与输入建立输入、目标与算法心智
沉岛:把访问过的陆地标记为 0
正在加载算法场景...
当前发生了什么
n×n 二进制矩阵 0→1 最短路径(八方向)。
机器状态
队列、8 方向、步数。
为什么正确
BFS 八邻居,首步即 1;注意对角。
不变量
BFS 首次到达即最短;八邻居都要尝试。
面试怎么说
0→1 BFS 八方向,步数+1;不可达 -1,O(n²)。
人类输入
n×n 二进制矩阵 0→1 最短路径(八方向)。
机制
BFS 八邻居,首步即 1;注意对角。
机器状态
队列、8 方向、步数。
可观察结果
从 (0,0) 到 (n-1,n-1) 最短步数(八方向)。
不变量
- · BFS 首次到达即最短;八邻居都要尝试。
常见误区
- · n=1 且 grid[0][0]=0 应返回 -1;注意边界。
迁移练习
- · LC994 腐烂橘子
- · LC127 单词接龙
面试怎么答
0→1 BFS 八方向,步数+1;不可达 -1,O(n²)。