迷宮解決使用圖表

Question

嘿，我是在當地的編程競賽，他們問我這個問題，我不能這樣做，請幫助我在這一個。

編寫一個程序，從一個文件加載迷宮的大小，然後迷宮本身。 要模擬迷宮，我們使用指定起始單元格的字符「S」，「。」指定空閒單元格，「＃」是牆，「F」是最後一個單元格。 編寫一個程序，該程序將查找從開始單元格到最終單元格的路徑。 你可以認爲在迷宮中有一個服從命令的機器人，所以對於下面的迷宮，機器人應該接收以下命令：向上，向上，向右，向右，向下，向下。

迷宮1個文本文件

5 5 
##### 
#...# 
#.#.# 
#S#T# 
##### 

迷宮2文本文件

4 5 
#.#.# 
#.#.# 
#S#T# 
##### 

一般寫程序（迷宮最大輸入可以是最多200×200）。

幫助將不勝感激。我只是一個冉冉升起的姊妹，所以如果你能夠提供我的代碼，那麼我可以理解它，並且他們會自己再做一次。

Answer 1

一個找到的路徑方式：

1. 有細胞的隊列進行檢查，並從那裏到目的地的每個單元步驟的數量。
2. 將結束單元格的計數設置爲0，並將其添加到隊列中。
3. 雖然隊列不爲空：
   1. 從隊列中獲取單元。
   2. 對於每個空閒鄰居小區，將當前小區的計數+ 1與鄰居小區的計數進行比較。如果較少，如果相鄰小區還沒有計數，則將相鄰小區的計數設置爲當前小區的計數+ 1，然後將相鄰小區添加到隊列中。

一旦隊列的空，在迷宮裏每個無細胞（可以從目標到達）將有中到目的地的最短路徑的步數。如果一個單元沒有計數，那麼就沒有從它到目的地的路徑。

如果起動電池具有計數，

1. 獲取起始細胞的數量。
2. 檢查每個相鄰單元的計數（count - 1）。有將是一個，這是路徑的下一步。記錄該單元格的方向，然後獲取該單元格，如果不是目標單元格，則對該單元格重複步驟2。

我會讓你知道如何加載迷宮。這是所有這些的簡單部分。

Answer 2

這裏的代碼太多了，但解決迷宮問題的最常見方法是在一個方向上出發，並且在每個右轉彎處都可以向右轉。

只要啓動和退出位於四個圍牆中的一箇中，就能保證工作。對於沒有沿着牆壁開始和退出的迷宮，這是遞歸練習。

看看你可以想出什麼代碼的基礎上，作爲一個起點！

HTH， 詹姆斯

Answer 3

如果你不知道該怎麼尋找： http://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm ，這包含了很多的詳細信息： http://www.astrolog.org/labyrnth/algrithm.htm