迷宮生成是圖論與隨機化演算法的經典應用。本文介紹兩種主流演算法：遞迴回溯器（原文版本）與標準隨機化 DFS（優化版），提供完整 C++ 實作、視覺化輸出與複雜度分析。
迷宮 = 矩形網格，每個格子為節點，相鄰格子間有牆。生成迷宮 = 找出一棵橫跨所有節點的生成樹（無環、連通）。
流程：
缺點：需額外記錄「已訪問」狀態、回溯邏輯較繁瑣、生成迷宮可能有細長死胡同。
關鍵洞見：只在「奇數座標」放置節點，偶數座標為牆。節點間隔一格，打通牆 = 將中間牆設為路。
#define MAZE_MAX 50
char maze[MAZE_MAX*2+3][MAZE_MAX*2+3]; // 實際陣列含邊界
int W, H; // 節點寬高 (如 11x11)
void init_maze(int w, int h) {
W = w; H = h;
int rows = H*2+1, cols = W*2+1;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
maze[r][c] = '#'; // 牆
// 邊界加厚（可選）
for (int c = 0; c < cols; c++) maze[0][c] = maze[rows-1][c] = '#';
for (int r = 0; r < rows; r++) maze[r][0] = maze[r][cols-1] = '#';
}
// 方向向量：右、下、左、上
const int dr[4] = {0, 1, 0, -1};
const int dc[4] = {1, 0, -1, 0};
void carve(int r, int c) {
// r,c 為節點索引 (0~W-1, 0~H-1)
// 實際陣列座標
int ar = r*2+1, ac = c*2+1;
maze[ar][ac] = ' '; // 標記為路
// 隨機打亂方向順序
int dirs[4] = {0,1,2,3};
for (int i = 3; i > 0; i--) {
int j = rand() % (i+1);
int tmp = dirs[i]; dirs[i] = dirs[j]; dirs[j] = tmp;
}
for (int d = 0; d < 4; d++) {
int nr = r + dr[dirs[d]];
int nc = c + dc[dirs[d]];
if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
int anar = nr*2+1, anac = nc*2+1;
if (maze[anar][anac] == ' ') continue; // 已訪問
// 打通中間牆
int wr = ar + dr[dirs[d]], wc = ac + dc[dirs[d]];
maze[wr][wc] = ' ';
carve(nr, nc); // 遞迴
}
}
int main() {
srand((unsigned)time(NULL));
init_maze(11, 11);
// 隨機起點
int sr = rand() % H, sc = rand() % W;
carve(sr, sc);
// 固定入口(左上)與出口(右下)
maze[1][0] = ' '; // 入口
maze[H*2-1][W*2] = ' '; // 出口
// 輸出
for (int r = 0; r < H*2+1; r++) {
for (int c = 0; c < W*2+1; c++)
putchar(maze[r][c]);
putchar('\n');
}
return 0;
}
##################### # # # # # # # ### # ##### # ### # # # # # # # ##### ### # ### # ### # # # # # # # # ########### # ### # # # # # ### ########### # # # # # # # # # #####################
#=牆，空格=路。入口左上，出口右下。
| 指標 | 數值 | 說明 |
|---|---|---|
| 時間 | O(V+E) = O(W×H) | 每個節點訪問一次，每條邊檢查常數次 |
| 空間 | O(W×H) | 迷宮陣列 + 遞迴堆疊 (深度 ≤ V) |
| 堆疊深度 | 最壞 O(W×H) | 極端情況可改用顯式堆疊迭代版 |
std::mt19937 + std::shuffle 替代 rand()，隨機品質更好uint8_t 或 bitset 存儲牆/路隨機化 DFS 是生成完美迷宮（任意兩點唯一路徑）的標準演算法。「節點間隔一格、打通中間牆」的座標映射技巧，將圖邊操作轉化為陣列索引運算，極大簡化實作。掌握此模式，可輕鬆擴展至迷宮遊戲、程序化地牢生成、機器人路徑規劃測試環境等應用。
