迷宮求解：C++ DFS + 棧 非遞歸實現

問題描述

給定 6×6 迷宮矩陣（0 為通道，1 為牆），從 (1,1) 起點走到 (6,6) 終點，輸出路徑坐標序列。

算法設計

• 使用棧模擬深度優先搜索（DFS），避免遞歸棧溢出。
• 每個狀態 PathUnit 包含 x, y, direct（下一個嘗試方向 0~3：下、右、上、左）。
• vecMark 記錄已訪問格子，防止重複搜索。
• 四個方向依次嘗試，走得通則壓棧繼續；走不通則 direct++ 嘗試下一方向；四個方向都試完則回溯（彈棧）。

核心代碼片段

[cpp]
struct PathUnit { int x, y, direct; };

class MyMaze {
    vector> vecMaze, vecMark;
public:
    MyMaze(int m,int n): vecMaze(m+2, vector(n+2)),
                         vecMark(m+2, vector(n+2)) {
        for (auto& row : vecMaze) fill(row.begin(), row.end(), 1); // 邊界圍牆
    }
    void InitMaze(string strMaze) { /* 解析字符串填充 vecMaze[1..m][1..n] */ }
    void ShowMaze() { /* 輸出矩陣 */ }

    void GetNextPath(const PathUnit& cur, PathUnit& next) {
        next = cur; next.direct = 0;
        switch(cur.direct) {
            case 0: next.x++; break; // 下
            case 1: next.y++; break; // 右
            case 2: next.x--; break; // 上
            case 3: next.y--; break; // 左
        }
    }
    bool GetOuter(const PathUnit& u) {
        return u.x == vecMaze[0].size()-2 && u.y == vecMark.size()-2;
    }
    void GetPath() {
        stack st;
        PathUnit unit{1,1,0};
        st.push(unit);
        bool bOver = false;
        while (!st.empty()) {
            PathUnit cur = st.top(); st.pop();
            while (cur.direct <= 3) {
                PathUnit next;
                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()) { auto& u = st.top(); cout<<"("<

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

(1,1,0)
(2,1,0)
(2,2,1)
...
(6,6,0)