迷宫中从起点到任意终点的最短步数怎么求?
哪些公司问过
答案要点
- 把格子看作节点、相邻可走格子看作边,边权均为 1
- BFS 按层扩展,第一次到达任意终点时的步数即最短
- 入队时标记已访问,避免重复入队
- 不可达时返回 -1;时间与空间复杂度均为 O(行 × 列)
- DFS 可判断连通性,但不能保证最短路径
易错点
- 出队时才标记已访问,导致同一格子多次入队
- 用 DFS 求最短路径
- 忘记检查起点本身就是终点或起点是墙的情况
面试官常见追问
- 如果要输出具体路径呢?
- 如果有多个起点呢?
- 如果每个格子的通过代价不同呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。