迷宮尋路演算法：堆疊實作深度優先搜尋

基於堆疊的迷宮解法完整實作

使用 C++ STL stack 實作深度優先搜尋（DFS）解決迷宮問題，展示路徑回溯與狀態管理的經典應用。

資料結構設計

struct PathUnit {
    int x, y;      // 當前座標
    int direct;    // 下一個嘗試方向 (0:下, 1:右, 2:上, 3:左)
};

MyMaze 類別核心實作

迷宮初始化與邊界處理

class MyMaze {
    vector<vector<int>> vecMaze;  // 迷宮地圖 (0:路, 1:牆)
    vector<vector<int>> vecMark;   // 走訪標記
    
public:
    MyMaze(int m, int n) 
        : vecMaze(m+2, vector<int>(n+2)), 
          vecMark(m+2, vector<int>(n+2)) {
        // 外圍填充牆壁，簡化邊界檢查
        for (auto& row : vecMaze)
            fill(row.begin(), row.end(), 1);
    }
    
    void InitMaze(string strMaze) {
        istringstream in(strMaze);
        for (int i = 1; i < (int)vecMaze.size(); i++)
            for (int j = 1; j < (int)vecMaze[0].size()-1; j++)
                in >> vecMaze[i][j];
    }
};

核心尋路演算法

void GetPath() {
    stack<PathUnit> st;
    PathUnit unit = {1, 1, 0};  // 起點 (1,1)
    st.push(unit);
    
    bool bOver = false;
    while (!st.empty()) {
        PathUnit cur = st.top(); st.pop();
        PathUnit next;
        
        while (cur.direct <= 3) {
            GetNextPath(cur, next);  // 根據方向計算下一格
            
            // 到達終點
            if (GetOuter(next)) {
                st.push(cur);
                st.push(next);
                bOver = true;
                break;
            }
            
            // 可通行且未走訪
            if (!vecMaze[next.y][next.x] && !vecMark[next.y][next.x]) {
                vecMark[next.y][next.x] = 1;
                st.push(cur);      // 保存當前點供回溯
                cur = next;        // 移動到下一點
            } else {
                cur.direct++;      // 嘗試下一方向
            }
        }
        if (bOver) break;
    }
    
    // 輸出路徑
    if (bOver) {
        while (!st.empty()) {
            PathUnit& u = st.top();
            cout << "(" << u.x << "," << u.y << "," << u.direct << ")" << endl;
            st.pop();
        }
    } else {
        cout << "this is no path" << endl;
    }
}

方向控制邏輯

void GetNextPath(const PathUnit& cur, PathUnit& next) {
    next = cur;
    next.direct = 0;
    switch (cur.direct) {
        case 0: next.x += 1; break;  // 向右
        case 1: next.y += 1; break;  // 向下
        case 2: next.x -= 1; break;  // 向左
        case 3: next.y -= 1; break;  // 向上
    }
}

bool GetOuter(const PathUnit& u) {
    int out_x = vecMaze[0].size() - 2;
    int out_y = vecMark.size() - 2;
    return (u.x == out_x && u.y == out_y);
}

測試案例

int main() {
    MyMaze m(6, 6);
    string s = "0 0 1 0 1 1 "
               "0 1 0 0 1 1 "
               "0 0 0 1 1 1 "
               "1 0 1 1 1 1 "
               "1 0 0 0 0 1 "
               "1 1 1 1 0 0";
    
    m.InitMaze(s);
    m.ShowMaze();
    m.GetPath();
    return 0;
}

演算法特點分析

關鍵設計亮點

1. 邊界擴充：迷宮四周加一層牆壁，省去邊界判斷邏輯
2. 方向狀態封裝：PathUnit 內建 direct 記錄嘗試進度，支援回溯後續續搜尋
3. 堆疊回溯機制：遇到死路自動彈出堆疊，回退至上一分叉點
4. 路徑重建：成功時堆疊中保存完整路徑節點

擴充方向

• 改用 BFS（佇列）尋找最短路徑
• 加入 A* 启發式搜尋提升效率
• 支援多終點、動態障礙物、權重地圖
• 圖形化介面即時顯示搜尋過程