迷宮是一個矩形區域, 左上角為迷宮的入口, 右下角為迷宮的出口

迷宮內部包含不可穿越的障礙物, 這些障礙物和迷宮的邊界平行

老鼠從入口進入迷宮, 尋找一條可行路徑使得老鼠可以從迷宮中走出, 要求路徑上不能存在障礙物. 除此之外, 要求路徑上的每一個位置都位於其相鄰位置的上、下、左或著右, 即不存在跳躍的路徑. 這樣的問題, 我們稱之為迷宮老鼠的問題

我們使用一個 m \times n 矩陣來表示迷宮, 不妨設為 A = (a_{ij})_{m \times n}. 其中, [latex]a_{11} 表示入口, a_{mn} 表示出口, mn 分別表示矩陣的行數和列數. 那麼有

a_{ij} = \begin {cases} 1, & 第\ i\ 行第\ j\ 列處存在障礙物 \\ 0, & 第\ i\ 行第\ j\ 列處可通行 \end {cases}

我們在玩迷宮遊戲的時候, 當發現一條路徑行不通時, 會回到之前的某一個路口走新的路徑, 這個惡路口一般是我們最後遇到的那個路口. 這個思想在演算法中被稱為回溯法. 由於是回到前一個遇到的路口, 因此我們通常需要保存路口, 每一次從最後保存的那個入口重新走, 自然地, 我們使用堆疊作為基本的資料結構

因為我們需要得到的是路徑, 而並不僅僅是路口, 所以我們需要將所有位置都放入到堆疊中. 首先以入口位置作為起始位置, 將其放入堆疊. 為了防止在尋路的過程中又繞回道已經走過的路徑, 對於已經到達過的路徑, 每一個位置上都放置一個障礙物, 即修改 a_{ij} = 1, 其中, i = 1, 2, ..., m, j = 1, 2, ..., n. 從起始位置開始, 每到達一個新的位置都將其放入堆疊中, 並放置障礙物. 接著, 檢查四周是否存在空閑位置, 如果有, 那麼就去空閑的位置; 如果沒有, 那麼將這個位置從堆疊中移除, 回到到達這個位置之前的那個位置. 不斷重複上述步驟, 若能到達終點, 則找到了一條從入口到出口的路徑; 如果最終回溯到了起點位置, 並且起點位置四周都被放置了障礙物, 那麼迷宮無解

在尋路的過程中, 每一個迷宮幾乎都會遇到某一個位置存在多個路口可以走. 此時, 我們作一個規定 : 優先檢測向下的路徑; 當向下的路徑無法到達的時候, 檢測向右的路徑; 當向右的路徑無法到達的時候, 檢測向上的路徑; 當向上的路徑無法到達的時候, 最後檢測向左的路徑. 也就是說, 對於空閑位置的檢查, 順序為下右上左. 當監測到有空閑位置可以走的時候, 不再繼續檢測, 直接到達那個空閑位置

當來到出口的時候, 堆疊中就保存著每一個位置. 從堆疊底部往頂部輸出, 就可以得到這個迷宮的一條路徑解. 但是由於堆疊無法從底部往頂部輸出, 因為每一次至多能取到頂部的元素, 就算是輸出, 也只是輸出了從出口到入口的路徑, 這是一條反向的路徑. 因此, 我們考慮使用資料結構改用向量 :

#include <vector>

template <std::size_t M, std::size_t N>
std::vector<std::pair<int, int>> find_path(bool (&maze)[M][N]) {
    constexpr std::pair<int, int> start_position {0, 0};
    constexpr std::pair<int, int> end_position {M - 1, N - 1};
    std::vector<std::pair<int, int>> path {};
    std::pair<int, int> position {0, 0};
    path.push_back(position);
    maze[position.first][position.second] = true;
    while(true) {
        if(position.first + 1 < M and not maze[position.first + 1][position.second]) {
            ++position.first;
            maze[position.first][position.second] = true;
            path.push_back(position);
            if(position == end_position) {
                break;
            }
        }else if(position.second + 1 < N and not maze[position.first][position.second + 1]) {
            ++position.second;
            maze[position.first][position.second] = true;
            path.push_back(position);
            if(position == end_position) {
                break;
            }
        }else if(position.first - 1 >= 0 and not maze[position.first - 1][position.second]) {
            --position.first;
            maze[position.first][position.second] = true;
            path.push_back(position);
            if(position == end_position) {
                break;
            }
        }else if(position.second - 1 >= 0 and not maze[position.first][position.second - 1]) {
            --position.second;
            maze[position.first][position.second] = true;
            path.push_back(position);
            if(position == end_position) {
                break;
            }
        }
        path.pop_back();
        position = path.back();
        if(position == start_position) {
            throw std::runtime_error("There is no way from entrance to export!");
        }
    }
    return path;
}

我們分析一下上述程式碼的複雜度. 在最好的情況下, 一直向下走然後一直向右走, 就可以從起始位置到達終點. 那麼總共需要經過 m + n - 1 個位置. 其中, mn 分別為矩陣的行數和列數. 在最壞的情況下, 需要把每一個位置都走一遍才能到達終點, 此時需要經過 m \cdot n 個位置. 因此, 這個程式的時間複雜度是 O(mn). 另外, 如果每一個位置都被保存入最終回傳的路徑中, 那麼還需要 m \cdot n + c 個輔助空間. 其中, c 為常數, 代表輔助變數所需要的額外空間. 因此, 這個程式碼的空間複雜度為 O(mn). 不過, 即使不存在任何障礙物, 上述程式碼也不可能每一個位置都走過去, 因此我們給出的最壞複雜度只是理論上可以達到的複雜度上限

值得注意的是, 上述方法並不一定能得到最短路徑. 如果要得到最短路徑, 我們需要借助佇列. 在起點和終點之間尋找一條最短路徑需要兩個過程 :

  1. 距離標記
  2. 路徑標記

由於最短路徑需要計算路徑的長度, 所以矩陣僅僅適用 0 或著 1 標識某一個位置是否具有障礙物就顯得不太夠用. 因此, 矩陣元素的值變為

a_{ij} = \begin {cases} -1, & 第\ i \ 行第\ j\ 列處存在障礙物 \\ 0, & 第\ i 行第\ j\ 列處可通行 \\ d(a_{ij}), & 第\ i\ 行第\ j\ 列距離起點\ a_{11}\ 的最短路徑長度 \end {cases}

設起點 a_{11} = 1, 那麼和起點相鄰且能夠達到的位置就被標記為 2. 類似的, 如果某個位置相鄰地位於被標記為 2 的位置, 並且這些位置可到達, 那麼這些位置的值被 3 標識. 不斷重複, 直到沒有任何位置可以被標記 (也就是迷宮無解) 或著到達了終點的時候停止標記. 標記結束之後, 並不是從起點移動到終點, 而是從終點開始向起點移動. 這樣, 演算法的時間複雜度能夠達到最小. 每一次向比當前位置的標記小 1 的位置移動, 直到到達起點位置為止

在距離標記的過程中, 我們需要佇列的幫助. 每一次標記完一個位置, 便將這個位置放入佇列當中. 當標記完成之後, 再從佇列中取出另外一個位置再次進行標記. 直到佇列中不再有元素可取位置 :

#include <stack>
#include <queue>

template <std::size_t M, std::size_t N>
int shortest_path(int (&maze)[M][N]) {
    std::queue<std::pair<int, int>> q;
    maze[0][0] = 1;
    q.push({0, 0});
    while(true) {
        auto position {q.front()};
        q.pop();
        bool in {};
        if(position.first + 1 < M and maze[position.first + 1][position.second] == 0) {
            maze[position.first + 1][position.second] = maze[position.first][position.second] + 1;
            ++position.first;
            q.push(position);
            in = true;
        }
        if(position.second + 1 < N and maze[position.first][position.second + 1] == 0) {
            maze[position.first][position.second + 1] = maze[position.first][position.second] + 1;
            ++position.second;
            q.push(position);
            in = true;
        }
        if(position.first - 1 >= 0 and maze[position.first - 1][position.second] == 0) {
            maze[position.first - 1][position.second] = maze[position.first][position.second] + 1;
            --position.first;
            q.push(position);
            in = true;
        }
        if(position.second - 1 >= 0 and maze[position.first][position.second - 1] == 0) {
            maze[position.first][position.second - 1] = maze[position.first][position.second] + 1;
            --position.second;
            q.push(position);
            in = true;
        }
        if(in) {
            continue;
        }
        if(q.empty()) {
            if(maze[M - 1][N - 1] == 0) {
                throw std::runtime_error("There is no way from entrance to export!");
            }
            break;
        }
    }
    return maze[M - 1][N - 1];
}
template <std::size_t M, std::size_t N>
std::stack<std::pair<int, int>> find_shortest_path(int (&maze)[M][N]) {
    constexpr std::pair<int, int> start_position {0, 0};
    std::stack<std::pair<int, int>> s;
    s.push({M - 1, N - 1});
    while(true) {
        auto position {s.top()};
        if(position == start_position) {
            break;
        }
        if(position.first - 1 >= 0 and maze[position.first - 1][position.second] == maze[position.first][position.second] - 1) {
            --position.first;
            s.push(position);
        }else if(position.second - 1 >= 0 and maze[position.first][position.second - 1] == maze[position.first][position.second] - 1) {
            --position.second;
            s.push(position);
        }else if(position.first + 1 < M and maze[position.first + 1][position.second] == maze[position.first][position.second] - 1) {
            ++position.first;
            s.push(position);
        }else if(position.second < N and maze[position.first][position.second + 1] == maze[position.first][position.second] - 1) {
            ++position.second;
            s.push(position);
        }
    }
    return s;
}

由於我們找到的最短路徑是從終點到起點的, 所以此處不再適用向量, 而是使用堆疊輸出. 上面函式的複雜度和之前尋找路徑的函式的複雜度相仿, 所以此處我們不再進行複雜度分析

以上在一些網格中尋找起點到終點的最短路徑的方法, 不只是適用於迷宮尋找最短路徑, 也適用於其它和網格有關的最短路徑的尋找, 比如網格電路佈線等等