5月 31, 2008

【演算】老鼠走迷宮 - Mouse in a Maze

@
  老鼠走迷宮是訓練使用堆疊(或是遞迴)的一種經典題型。老鼠可以往上、下、左、右四個方向前進,你必須讓這隻老鼠在迷宮中,由給定的起點走到終點。

  而這題最簡單的作法,就是由起點開始向四個方向測試,並將走過的路徑做個標示,以防止走過相同的路。一旦發現現在的走法無法走到終點,則追朔回之前的路徑,並將當前的標示清除。

  這樣敘述或許比較抽象。假設迷宮的起點在(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那個檔案?
謝謝!

thock90 提到...

能將檔案處理好嗎??

Chi-En Wu 提到...

不好意思,我先前的檔案好像被我誤刪,找不到了
雖然有備份,但是不曉得擺到哪邊去了,也許還要一點時間尋找....

張貼留言