C++使用回溯算法解決簡(jiǎn)單迷宮問(wèn)題

給你一個(gè)矩陣，如何在其中找到一條通路呢？

（是不是很凌亂？^_^）

在C++中怎么實(shí)現(xiàn)呢？

較好的解決方案：使用棧解決。

解決思路：

1. 使用FILE*和open預(yù)先打開(kāi)文件（絕對(duì)路徑和相對(duì)路徑¹），注意斷言。

2. 正確讀取文件，判斷字符和空格，空格略過(guò)，讀取字符。

3. 從入口進(jìn)入，每走一步，判斷上下左右4個(gè)方向有無(wú)道路。

4. 如果4個(gè)方向有路，則按次序先進(jìn)入其中一條（將字符壓棧push），并將所走過(guò)字符重置數(shù)字（后面回溯）。

5. 如果4個(gè)方向沒(méi)有，則出棧pop，即回溯，并再次判斷。

6. 逐次循環(huán)，直至判斷下一個(gè)有效節(jié)點(diǎn)為邊界時(shí)出棧，此時(shí)重置數(shù)字的路徑即為通路。

注釋?zhuān)?/span>

1. 1.       相對(duì)路徑和絕對(duì)路徑：絕對(duì)路徑：是從盤(pán)符開(kāi)始的路徑，形如C:\windows\system32\cmd.exe相對(duì)路徑：是從當(dāng)前路徑開(kāi)始的路徑，假如當(dāng)前路徑為C:\windows要描述上述路徑，只需輸入system32\cmd.exe。實(shí)際上，嚴(yán)格的相對(duì)路徑寫(xiě)法應(yīng)為.\system32\cmd.exe其中，.表示當(dāng)前路徑，在通道情況下可以省略，只有在特殊的情況下不能省略。

2. 2.       此次實(shí)現(xiàn)中為簡(jiǎn)單實(shí)現(xiàn)采用相對(duì)路徑，將寫(xiě)好的“迷宮”放在同一項(xiàng)目文件下進(jìn)行打開(kāi)即可

下面為C++代碼的簡(jiǎn)單實(shí)現(xiàn)：

預(yù)處理：

預(yù)先打開(kāi)文件及處理字符

從入口節(jié)點(diǎn)開(kāi)始判斷：

回溯算法：

最后一步，測(cè)試單元：

哈哈！完成，開(kāi)始測(cè)試。

似乎很成功哦！但是并沒(méi)有測(cè)試另一條路徑（雖然不同），把剛才函數(shù)的上下左右重新調(diào)整一下，再運(yùn)行：

依舊成功！

此時(shí)，就算我們的迷宮問(wèn)題就算小小的解決了吧，當(dāng)然，有興趣的童鞋可以再加探索，比如如何達(dá)到最短測(cè)試路徑等。就不在此一一深究了。畢竟這個(gè)看似小小的程序也是小弟耗費(fèi)一番心思的成品，謝謝大家的閱讀啦！有興趣可以關(guān)注哦！嘿嘿。