DFS 回溯法解决迷宫问题课堂笔记

一、方案总数统计

问题概述

在 n×m 迷宫中，给定起点 (sx, sy) 和终点 (ex, ey)，部分格子为障碍物。统计从起点到终点的所有不重复路径数量（每个格子仅走一次，上下左右移动）。

核心思路

1. 用 vis[x][y] 标记当前格子已访问，防止重复走。
2. 递归探索下一格，探索结束后取消标记（回溯），让其他路径可使用该格子。
3. 到达终点时，方案数 ans++。

核心代码片段

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; // 右、左、下、上
int vis[10][10], ans;

void dfs(int x, int y) {
    if (x == ex && y == ey) { ans++; return; }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 0 && vis[nx][ny] == 0) {
            vis[nx][ny] = 1;
            dfs(nx, ny);
            vis[nx][ny] = 0; // 回溯
        }
    }
}

注意事项

• 起点需提前标记 vis[sx][sy] = 1。
• 迷宫大小建议 ≤ 10×10（回溯法时间复杂度高）。

二、最短路径求解

问题概述

在 n×m 迷宫中，格子为 .（可通行），求从左上角 (1,1) 到右下角 (n,m) 的最短路径步数。

核心思路

1. 递归函数携带 step 参数，记录从起点到当前格子的步数。
2. 到达终点时，更新全局最短路径 ans = min(ans, step)。
3. 探索过程中用 vis 数组标记，递归后回溯。

核心代码片段

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int vis[50][50], ans = 1e9; // ans 初始化为极大值
char c[50][50];

void dfs(int x, int y, int step) {
    if (x == n && y == m) { ans = min(ans, step); return; }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0 && c[nx][ny] == '.') {
            vis[nx][ny] = 1;
            dfs(nx, ny, step + 1);
            vis[nx][ny] = 0; // 回溯
        }
    }
}

注意事项

• ans 需初始化为极大值（如 1e9）。
• 若迷宫较大，建议用 BFS（更适合求最短路径）。

三、路径存储与输出

问题概述

在 n×m 迷宫中，给定起点 (sx, sy) 和终点 (ex, ey)，格子为 1（可通行）。统计所有路径，并按格式输出坐标（如 (1,1)->(1,2)->(2,2)）。

核心思路

1. 递归函数携带 string rec 参数，记录每一步的方向（将方向索引 i 转为字符串存入 rec）。
2. 到达终点时，根据 rec 中的方向序列还原路径并输出。

核心代码片段

// 方向：左、上、右、下（对应 i=0,1,2,3）
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int vis[100][100], ans;

void dfs(int x, int y, string rec) {
    if (x == ex && y == ey) {
        ans++;
        cout << "(" << sx << "," << sy << ")";
        int x = sx, y = sy;
        for (int i = 0; i < rec.size(); i++) {
            int num = rec[i] - '0';
            x += dx[num], y += dy[num];
            cout << "->" << "(" << x << "," << y << ")";
        }
        cout << endl;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0 && a[nx][ny] == 1) {
            vis[nx][ny] = 1;
            dfs(nx, ny, rec + to_string(i));
            vis[nx][ny] = 0; // 回溯
        }
    }
}

注意事项

• 起点或终点为 0 时，直接输出 -1。
• 方向数组 dx[]、dy[] 需与 rec 中索引严格对应。