而這題最簡單的作法,就是由起點開始向四個方向測試,並將走過的路徑做個標示,以防止走過相同的路。一旦發現現在的走法無法走到終點,則追朔回之前的路徑,並將當前的標示清除。
這樣敘述或許比較抽象。假設迷宮的起點在(XS, YS)、終點在(XE, YE)。迷宮存在 maze 這個二維陣列之中,若 maze[x][y] = 1 則代表牆壁,maze[x][y] = 0 則代表可以通行。那麼,解題的虛擬碼就像這樣:
bool visit(index x, index y) { bool success = false; gone[x][y] = true; if ((maze[x][y + 1] != 1 and visit(x, y + 1) = true) or (maze[x + 1][y] != 1 and visit(x + 1, y) = true) or (maze[x][y - 1] != 1 and visit(x, y - 1) = true) or (maze[x - 1][y] != 1 and visit(x - 1, y) = true)) { success = true; } else { gone[x][y] = false; } return success; }
假如還是不太瞭解,我有使用 C++ 以這個方式,作出一個老鼠走迷宮的範例:
程式採用標準輸入,第一行的兩個數字 n, m 代表迷宮的高與寬。接下來的 n * m 個數字代表迷宮,1 代表牆壁、0 代表可以通行。最後的四個數字分別代表起點的 x 座標、起點的 y 座標、終點的 x 座標、終點的 y 座標。
附屬的文字檔是我做出來的範例迷宮。假如要使用則在命令列模式,至該檔案目錄輸入以下指令:
Maze < Maze.txt
除此之外,若是想看到老鼠尋路的方式,可以輸入以下指令(紅字請自行更改,代表每一步延遲多久。單位是千分之ㄧ秒):
Maze < Maze.txt 500
3 回覆:
是否能夠再一次PO那個檔案?
謝謝!
能將檔案處理好嗎??
不好意思,我先前的檔案好像被我誤刪,找不到了
雖然有備份,但是不曉得擺到哪邊去了,也許還要一點時間尋找....
張貼留言