狗家电面 12/14

刚结束的加面, 国人小哥 满满凉意..
[hide=200

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
)">[/hide]


补充内容 (2018-12-14 19:00):
矩阵里面有墙, 只能走空的位置

bfs也可以返回路径吧

xiaoduoduo 发表于 2018-12-14 21:02
bfs也可以返回路径吧

是的 我挂了电话才想通

返回路径的话，可以每个点记录最短路径的上一个点在哪里。

请问是不是bfs从起点开始update了map，然后从终点倒着走？

insomnia001 发表于 2018-12-28 21:19
请问是不是bfs从起点开始update了map，然后从终点倒着走？

是这个思路, map保存每个点对应的上一步位置 和 路径

BFS的Queue里面，里面维护从src出发的所有的路径，使用explored set去避免重复探索Cell，最先到达的路径就是最短路径。复杂度O(N)。
DFS可以用一个HashMap<Cell, 最短那个路径>剪枝，只展开当前来看最短的路径。复杂度O(N)。