“唰唰！”，牛仔从大树上跳下来。

然后，他看见了倒在地上，奄奄一息的小机器人罗比。

“哥们，发生啥事了？”

杨成看了看小机器人，脸上很是诧异。

就在这时，罗比开口了，它的声音很微弱。

“主人...”

“罗比的寻路逻辑被破坏了...”

“想让罗比带你们回家...”

“请先修复...”

杨成听到这里，已经有了些眉目。

这个关卡敢情是考寻路算法啊。

对于要判定地图中两点间的路径，有一种简单粗暴的做法。

使用深度优先遍历！

它的实现方式很简单，但有2点不足：

1.效率低下

2.它找到的路径不一定是最短路径

第二点尤其致命，绕远路白费力气。

所以这个问题应该是寻找图中两点的最短路径。

当前的地图有什么特点？

它并没有“权重”。

对于有权重的地图，寻找最小权重和路径，有一种经典的算法。

迪杰斯特拉最短路径算法。

但这个地图是没有权重的。

事实上，这里也可以应用迪杰斯特拉算法，但效率不高，而且需要大量的额外空间。

怎样找到一种，足够简单，实现方便，而且效率不会很低的最短路径算法呢？

杨成想到了老朋友。

广度优先遍历算法。

这个方法可以做到！

但是，我们得给它做点小小的改变。

-------------------------------

这个最短路径问题，迪杰斯特拉算法经过优化后的时间效率是O（N*logN），而广度优先遍历是O（N）的，而且迪杰斯特拉需要的额外空间也更多。

Loading...

未加载完，尝试【刷新】or【关闭小说模式】or【关闭广告屏蔽】。

尝试更换【Firefox浏览器】or【Chrome谷歌浏览器】打开多多收藏！

移动流量偶尔打不开，可以切换电信、联通、Wifi。

收藏网址：www.dd123.cc

(＞人＜；)