微末电面

一道简单的bfs，套用了一些无人车的场景。如果board无限大，但是点很稀疏，怎么定义这个boa

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

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

印出来。我最后写打印路径的时候写出了bug，最后挂了。求加米！

要路徑的話只能recursive不能queue吧？

这道应该怎么做呢？
dfs求最短路径效率太低了，还有没有更好的办法呢？

hsierra 发表于 2020-11-17 16:37
这道应该怎么做呢？
dfs求最短路径效率太低了，还有没有更好的办法呢？

是不是可以用bfs一步一步走，每个位置只存最短路径的上一个位置（parent），最后回溯一下，如果有很多可行路径，可能要用hash表来存parent（like a tree），然后dfs回溯

定义一个数据结构
class Node {
public:   // constructor
  ...
  // destructor
  ...

  pair<int, int> position;
  int sum;
  Node* previous;
};

bfs结束用node->previous从尾到头把路径找出来。