迷宮路徑查找 - 棧 (DFS) 與隊列 (BFS) 雙重實現

問題描述

15×15 迷宮，1 為牆，0 為路，2 起點，3 終點。分別用棧（深度優先）和隊列（廣度優先）找路徑並標記輸出。

棧實現 (DFS) - 路徑權值標記法

• 起點權值 4，唯一出口繼承權值，分支點入棧並遞增權值。
• 回溯時出棧，權值+1，保證最終路徑權值遞增。
• 輸出時從起點貪心選擇權值最大的鄰居，標記為路徑 (-1)。

隊列實現 (BFS) - 逆向最小權值法

• 從起點廣度優先，同層節點賦予相同權值，層層遞增。
• 輸出時從終點逆向，選擇權值比當前小 1 的鄰居，標記路徑。

完整代碼結構（C++）

#include 
#include 
#include 
using namespace std;
const int N = 15;
int maze[N][N] = { ... }; // 迷宮數據
struct Point { int x, y; };

void findStartEnd(Point& s, Point& e) { ... }
void initMaze() { ... } // 恢復原始數據

void dfsWithStack(Point s, Point e) { ... } // 棧版邏輯
void bfsWithQueue(Point s, Point e) { ... } // 隊列版邏輯
void printPathDFS(Point s) { ... } // 從起點順向輸出
void printPathBFS(Point e) { ... } // 從終點逆向輸出

int main() {
    Point start, end;
    findStartEnd(start, end);
    dfsWithStack(start, end);
    printPathDFS(start);
    initMaze();
    bfsWithQueue(start, end);
    printPathBFS(end);
    return 0;
}

完整代碼較長，核心在於權值標記策略與路徑回溯方式的差異。DFS 適合找任意一條路，BFS 保證最短路徑。