“唰唰,！”

　　牛仔從大樹上面跳下來,。

　　然后，他看見了倒在地上，奄奄一息的小機(jī)器人羅比,。

　　“哥們,，發(fā)生啥事了,？”

　　楊成趕緊爬起來,，毫發(fā)無損，看了看小機(jī)器人,，臉上很是詫異,。

　　就在這時，羅比開口了,，它的聲音很微弱,。

　　“主人...”

　　“羅比的尋路邏輯被破壞了...”

　　“如果想讓羅比帶你們回家...”

　　“請先編寫代碼修復(fù)...”

　　楊成聽到這里，已經(jīng)有了些眉目,。

　　這個關(guān)卡敢情是考查尋路算法?。?p>　　對于要找到地圖中,，兩個點之間的路徑,，有一種簡單而粗暴的做法。

　　從出發(fā)點使用深度優(yōu)先遍歷,，如果達(dá)到了終點,，就終止并返回路徑。

　　它的實現(xiàn)方式很簡單,，但是有兩點不足：

　　1.效率低下

　　2.它找到的路徑不一定是最短路徑,，很有可能會繞遠(yuǎn)路。

　　第二點尤其糟糕,，繞遠(yuǎn)路白費力氣吶...

　　所以,，這個問題應(yīng)該是尋找圖中兩點間的最短路徑。

　　楊成很快想到了,，有一種經(jīng)典的算法：

　　迪杰斯特拉最短路徑算法,。

　　還有另一種簡潔的解法，廣度優(yōu)先遍歷,。

　　它們都很合適,。

　　但從效率上來說,，還是有細(xì)微的差別。

　　迪杰斯特拉算法經(jīng)過優(yōu)化后的時間復(fù)雜度是：

　　O（N*logN）

　　廣度優(yōu)先遍歷是O（N）,。

　　然后空間效率,，在一般情況下，迪杰斯特拉需要的額外空間更多,。

　?。˙readth-First Search）

　　就是你了，BFS,！

　　它足夠簡單,，實現(xiàn)方便，而且效率也不會很低...