您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

演算法實作筆記：迷宮尋路——回溯法（DFS）完整教學與 C 語言實作

編輯：關於C

問題描述

給定一個二維網格迷宮，1 代表可通行路徑，0 代表牆壁，2 代表終點。從起點 (1,0) 出發，只能上下左右四向移動，尋找一條到達終點的路徑（或列舉所有路徑）。

核心演算法：深度優先搜尋 + 回溯

本質是對「狀態空間樹」的前序遍歷：

在當前格 (x,y)，若合法且未訪問，標記為已訪問。
若為終點，記錄/列印路徑，返回成功。
否則按固定順序（如上、左、下、右）遞迴嘗試四鄰居。
若四方向皆失敗，撤銷標記（回溯），返回失敗。

資料結構設計


#define MAX_N 100

int maze[MAX_N][MAX_N];      // 原始迷宮：0=牆, 1=路, 2=終點
int visited[MAX_N][MAX_N];   // 0=未訪問, 1=路徑上, 2=已嘗試失敗(可選)
int path_x[MAX_N*MAX_N];     // 路徑座標記錄
int path_y[MAX_N*MAX_N];
int path_len = 0;

合法性檢查


bool is_valid(int x, int y, int n) {
    return x >= 0 && x < n && y >= 0 && y < n &&  // 邊界
           maze[x][y] != 0 &&                       // 非牆壁
           visited[x][y] == 0;                      // 未訪問
}

尋找單一路徑（停於第一解）


bool dfs_find_one(int x, int y, int n) {
    if (!is_valid(x, y, n)) return false;

    visited[x][y] = 1;
    path_x[path_len] = x;
    path_y[path_len] = y;
    path_len++;

    if (maze[x][y] == 2) return true;  // 找到終點

    // 四方向順序可影響找到的具體路徑
    if (dfs_find_one(x-1, y, n)) return true;  // 上
    if (dfs_find_one(x, y-1, n)) return true;  // 左
    if (dfs_find_one(x+1, y, n)) return true;  // 下
    if (dfs_find_one(x, y+1, n)) return true;  // 右

    // 回溯
    path_len--;
    visited[x][y] = 0;
    return false;
}

列舉所有路徑


void dfs_find_all(int x, int y, int n) {
    if (!is_valid(x, y, n)) return;

    visited[x][y] = 1;
    path_x[path_len] = x;
    path_y[path_len] = y;
    path_len++;

    if (maze[x][y] == 2) {
        print_path();  // 列印當前路徑
    } else {
        dfs_find_all(x-1, y, n);
        dfs_find_all(x, y-1, n);
        dfs_find_all(x+1, y, n);
        dfs_find_all(x, y+1, n);
    }

    path_len--;
    visited[x][y] = 0;
}

路徑列印


void print_path(void) {
    for (int i = 0; i < path_len; ++i) {
        printf("(%d,%d) ", path_x[i], path_y[i]);
    }
    putchar('\n');
}

測試案例


void test_maze(void) {
    int n = 6;
    int init[6][6] = {
        {0,0,0,0,1,1},
        {1,1,0,0,1,0},
        {0,1,1,1,1,0},
        {0,0,1,0,1,2},
        {0,0,1,0,1,0},
        {0,0,1,1,1,0}
    };
    memcpy(maze, init, sizeof(init));
    memset(visited, 0, sizeof(visited));
    path_len = 0;

    if (dfs_find_one(1, 0, n)) {
        printf("Found path:\n");
        print_path();
    } else {
        puts("No path");
    }

    // 列舉所有路徑
    memset(visited, 0, sizeof(visited));
    path_len = 0;
    printf("\nAll paths:\n");
    dfs_find_all(1, 0, n);
}

複雜度分析

指標	數值	說明
時間複雜度	O(4^n²)	最壞情況（全通路網格），每個格嘗試 4 方向
空間複雜度	O(n²)	visited 陣列 + 遞迴棧深度 + 路徑記錄
最優路徑	不保證	DFS 找到的第一解非最短路徑

關鍵優化與變體

方向啟發式：優先朝終點方向搜尋（如曼哈頓距離遞減），大幅縮減搜尋樹。
迭代加深 DFS (IDDFS)：限制深度逐層加深，兼具 BFS 完整性與 DFS 空間效率。
A* 演算法：引入啟發函數 f = g + h，保證找到最短路徑，工程首選。
位元壓縮：visited 用 uint64_t 位圖，加速複製與檢查（適合 n ≤ 8）。
非遞迴棧：手動模擬棧避免遞迴限制，支援超大迷宮。

常見錯誤避坑

錯誤	後果	修正
忘記回溯時清除 `visited`	後續路徑誤判為已訪問，漏解	退出遞迴前 `visited[x][y]=0`
邊界檢查順序錯誤	先存取 `maze[x][y]` 再檢查邊界 → 段錯誤	先檢查 `x,y` 範圍
起點/終點本身為牆壁	直接返回無解	進入 DFS 前驗證 `maze[sx][sy]!=0 && maze[tx][ty]!=0`
路徑記錄陣列溢出	緩衝區溢出	分配 `n*n` 大小或動態擴展

總結

回溯法是解決「約束滿足、路徑搜尋、組合生成」問題的通用模板。迷宮尋路通過「標記 → 遞迴 → 回溯」三步曲，直觀展示了 DFS 對狀態空間的完整遍歷。工程上：單解用 DFS+啟發式，最短路徑用 BFS/A*，全路徑枚舉用 DFS+回溯。掌握此模板，可無縫遷移至 N 皇后、數獨求解、圖論 Hamiltonian 路徑等經典問題。