ponyai电面

ponyai电面

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

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

求大家多加大米，谢谢！

请问LZ怎么做的这题啊？
直觉上肯定不能每个起点都搜一次，但是又不知道该怎么offset。。

raistlins 发表于 2019-3-9 14:06
请问LZ怎么做的这题啊？
直觉上肯定不能每个起点都搜一次，但是又不知道该怎么offset。。

这题因为在格子上走，每走一步距离+1，所以用BFS就行。先把所有起点加到queue里，然后遍历没有访问过的节点就好了。
如果每走一步距离不是+1而是输入的不同的长度的话，就完全用图论方法做。加上一个超级起点，把这个超级起点和所有普通起点相连，边长度为0。然后从超级起点开始走，求到每个节点的最短路径。