演算法 - 老鼠走迷宮

老鼠走迷宮為演算法中較基本的題型，給一迷宮圖形，畫出起點到終點的解法與解法數量，亦或是算出解法步數，都可以利用以下程式算出。

與大部分的演算法相同，老鼠走迷宮是利用遞迴的特性，使得老鼠能判斷上下左右是否有路，並且走到死路能回頭再找別的路走。
以下例子為左上走到右下的迷宮。
input:
8 7
..XXXXXX
X......X
X.X.XX.X
X.X.X..X
XXX.XXXX
X......X
XXXXXX..

output:
--XXXXXX
X---...X
X.X-XX.X
X.X-X..X
XXX-XXXX
X..----X
XXXXXX--

以C#為例子，用String.Split讀取 row 與 col：

string line = Console.ReadLine();
string[] value = line.Split(new string[]{" "}, 
          StringSplitOptions.RemoveEmptyEntries);
int col = Convert.ToInt32(value[0]);
int row = Convert.ToInt32(value[1]);

接著宣告一個 char 二維陣列，讀入迷宮的資料：

int eRowIndex = row - 1;
int eColIndex = col - 1;

char[,] maze = new char[row, col];
for (int i = 0; i < row; i++)
{
    char[] mazeTmp = Console.ReadLine().ToCharArray();
    for (int j = 0; j < mazeTmp.Length; j++)
        maze[i, j] = mazeTmp[j];
}
Console.WriteLine();

接下來是遞迴函式就是在模擬老鼠走法，每一步老鼠會做記號 ( 改為 '-' ) 並且判斷是否已經到了終點，如果未到終點，老鼠會嘗試上下左右是否有路，如果有路，接著往有路的方向呼叫函式；如果沒有路，就將此點記號取消 ( 改為 '.' )，如此一來，所有走到死路的走法都會回頭到岔路繼續往別的方向嘗試，最後，就會走到終點。

static void visit(int nRI, int nCI, int eRI, int eCI, char[,] maze)
{
    maze[nRI, nCI] = '-';
    if (nRI == eRI && nCI == eCI)
        print(maze);

    if (!(nRI - 1 < 0) && maze[nRI - 1,nCI] == '.') // 上
        visit(nRI - 1, nCI, eRI, eCI, maze);
    if (!(nCI - 1 < 0) && maze[nRI, nCI - 1] == '.') // 左
        visit(nRI, nCI - 1, eRI, eCI, maze);
    if (nRI + 1 <= eRI && maze[nRI + 1, nCI] == '.') // 下
        visit(nRI + 1, nCI, eRI, eCI, maze);
    if (nCI + 1 <= eCI && maze[nRI, nCI + 1] == '.') // 右
        visit(nRI, nCI + 1, eRI, eCI, maze);

    maze[nRI, nCI] = '.';
}

static void print(char[,] maze)
{
    for (int i = 0; i < maze.GetLength(0); i++)
    {
        for (int j = 0; j < maze.GetLength(1); j++)
            Console.Write(maze[i, j]);
        Console.WriteLine();
    }
    Console.WriteLine();
}

最後，只要傳入起點位置與終點位置與迷宮陣列，即能將解法輸出：
visit(0, 0, eRowIndex, eColIndex, maze);

回首頁