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

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

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

　　這樣敘述或許比較抽象。假設迷宮的起點在(X_S, Y_S)、終點在(X_E, Y_E)。迷宮存在 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