問題描述

10×10 迷宮，0 通路，1 牆壁。從入口 (2,0) 走到邊界任意出口。用棧實現 DFS 回溯，記錄所有路徑並找出最短路徑。

核心數據結構

• Pos：座標結構體 {row, col}
• stack path：當前探索路徑
• stack minPath：最短路徑記錄
• maze[][]：0 未訪問，1 牆壁，2 已訪問

算法流程

1. 入口入棧，標記為 2
2. 循環：取棧頂當前位置，嘗試上下左右 4 方向
   • 下一位置合法（邊界內、值為 0） → 入棧、標記 2、continue 深入
   • 4 方向都不可走 → 出棧回溯
3. 到達邊界（出口）：
   • 若 minPath 為空或當前路徑更短 → 更新 minPath = path
   • 出棧繼續尋找其他路徑
4. 棧空 → 結束，輸出最短路徑

完整代碼

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
using namespace std;

#define N 10

struct Pos { size_t _row, _col; };
stack minPath; // 全局最短路徑

void InitMaze(int maze[][N], int size) {
    FILE* fp = fopen("MazeMap.txt", "r");
    if (!fp) { cout << "open fail\n"; exit(-1); }
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ) {
            char ch = fgetc(fp);
            if (ch == EOF) { cout << "init fail\n"; exit(-1); }
            if (ch == '0' || ch == '1') {
                maze[i][j] = ch - '0';
                ++j;
            }
        }
    }
    fclose(fp);
}

void DisplayMaze(int maze[][N], int size) {
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) cout << maze[i][j] << " ";
        cout << endl;
    }
    cout << endl;
}

bool CheckAccess(int maze[][N], Pos next) {
    return next._row < N && next._col < N && maze[next._row][next._col] == 0;
}

bool GetMazePath(int maze[][N], Pos entry, stack& path) {
    path.push(entry);
    maze[entry._row][entry._col] = 2;

    while (!path.empty()) {
        Pos cur = path.top();
        // 到達邊界（出口）
        if (cur._row == 0 || cur._row == N-1 || cur._col == 0 || cur._col == N-1) {
            if (minPath.empty() || path.size() < minPath.size())
                minPath = path; // 棧支持拷貝賦值
            path.pop();
            continue;
        }
        Pos next = cur;
        // 嘗試 4 方向：上、下、左、右
        next._row -= 1; // 上
        if (CheckAccess(maze, next)) { path.push(next); maze[next._row][next._col] = 2; continue; }
        next = cur; next._row += 1; // 下
        if (CheckAccess(maze, next)) { path.push(next); maze[next._row][next._col] = 2; continue; }
        next = cur; next._col -= 1; // 左
        if (CheckAccess(maze, next)) { path.push(next); maze[next._row][next._col] = 2; continue; }
        next = cur; next._col += 1; // 右
        if (CheckAccess(maze, next)) { path.push(next); maze[next._row][next._col] = 2; continue; }
        // 死路，回溯
        path.pop();
    }
    return true; // 找完所有路徑
}

int main() {
    int maze[N][N] = {0};
    InitMaze(maze, N);
    DisplayMaze(maze, N);

    stack path;
    Pos entry = {2, 0};
    GetMazePath(maze, entry, path);

    cout << "succeed to get out\n";
    DisplayMaze(maze, N);
    cout << "the shortest path is\n";
    while (!minPath.empty()) {
        cout << "<" << minPath.top()._row << "," << minPath.top()._col << "><-";
        minPath.pop();
    }
    return 0;
}

關鍵點說明

• 文件讀取：fgetc 逐字符讀，跳過換行符
• 標記 2：防止重複訪問，回溯時不恢復 0（DFS 標準做法）
• 最短路徑：利用棧拷貝賦值 minPath = path 記錄當前最優路徑
• 方向順序影響找到路徑的順序，但不影響最短路徑結果

局限性

DFS 非最優路徑搜索算法（不保證最先找到最短路）。本題規模小（10×10）可接受。大規模迷宮應用 BFS（保證最短步數）或 A* 算法。