迷宫 - 题目列表

形式化题目

给定一个 $N \times M$ 的网格，其中有 $T$ 个格子是障碍（不可进入），另有起点 $S$ 和终点 $E$ 。每一步可以从当前格子移动到相邻的上、下、左、右格子，但每个格子最多经过一次。求从 $S$ 到 $E$ 的不同路径数量。

思路

这道题没有「先写暴力、再优化」的层次：DFS 回溯本身就是最直接的朴素解法，单独写一个暴力只会把最终代码再抄一遍，所以直接讲最终做法。

一条路径可以看成一串「上下左右」的方向选择：从起点开始，每一步从四个方向里选一个合法方向，走到终点时这些选择串起来就是一条完整路径。这和 rbook 的《递归实现多重循环》是同一个模型——每层递归只负责一次选择，dfs(x, y) 里的四方向循环就是枚举这一层的所有选择。

「每个格子最多经过一次」用 vis 数组实现，它只记录当前这条路径走过的格子，这是 DFS 回溯的精髓，对应 rbook《递归的前进与回溯》的两个阶段：

前进阶段：进入下一格前 vis[nx][ny] = 1；
回溯阶段：递归返回后 vis[nx][ny] = 0，把格子还给兄弟分支。

如果只标记不撤销，第一条分支走过的格子会永远被封锁，其他路径就会被错误地漏掉。

下面这张 ASCII 图展示样例迷宫的结构（起点 $S$ 、终点 $E$ 、障碍 #）：

text

1
2
3
4
5
62 x 2 迷宫，障碍在 (1,2)
+---+---+
| S | # |
+---+---+
|   | E |
+---+---+

从 (1,1) 出发只有一条合法路径：先向下到 (2,1)，再向右到 (2,2)。(1,2) 是障碍不能走，(1,1) 已标记不能绕回，所以答案是 1。

实现上：blocked 数组记录障碍，起点在进入 DFS 前标记为已访问，防止路径绕回起点造成重复计数；dx[4] / dy[4] 方向数组把「四个方向」写成一次循环；到达终点时 ans++ 并返回，因为继续从终点扩展只会走重复格子。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-13 13:29
 * update_at: 2026-08-13 13:40
 */
/* P1605 迷宫 */
/* DFS 回溯：统计从起点到终点的所有简单路径数量。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n, m, t;              // 迷宫长宽与障碍数量
int sx, sy, fx, fy;       // 起点与终点坐标
int blocked[MAXN][MAXN];  // blocked[x][y] = 1 表示 (x, y) 是障碍
int vis[MAXN][MAXN];      // vis[x][y] = 1 表示 (x, y) 在当前路径上已访问
long long ans;            // 路径总数
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

// 从 (x, y) 出发 DFS，每到达一次终点就找到一条完整路径。
void dfs(int x, int y) {
    if (x == fx && y == fy) {  // 到达终点，统计当前这条路径
        ans++;
        return;
    }

    // 这一层递归枚举四个方向的选择。
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;  // 出界
        if (blocked[nx][ny] || vis[nx][ny]) continue;        // 障碍或已访问

        vis[nx][ny] = 1;  // 前进阶段：标记进入
        dfs(nx, ny);
        vis[nx][ny] = 0;  // 回溯阶段：撤销标记
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> t;
    cin >> sx >> sy >> fx >> fy;

    for (int i = 1; i <= t; i++) {
        int x, y;
        cin >> x >> y;
        blocked[x][y] = 1;
    }

    vis[sx][sy] = 1;  // 起点视为已访问，防止路径绕回起点
    dfs(sx, sy);
    cout << ans << '\n';
    return 0;
}

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 14:54
 * update_at: 2026-08-14 14:54
 */
/* P1605 迷宫：网格 DFS，访问标记与回溯恢复。 */

#include <iostream>

const int max_n = 15;  // N、M 最大为 5，留出余量

int rows, cols;                 // 迷宫长宽
int obstacle_count;             // 障碍个数
int start_row, start_col;       // 起点坐标
int end_row, end_col;           // 终点坐标
int blocked[max_n][max_n];      // blocked[row][col] = 1 表示障碍，不可走
int visited[max_n][max_n];      // visited[row][col] = 1 表示在当前路径上已走过
int path_count = 0;             // 从起点到终点的方案总数
int dir_row[4] = {0, 0, 1, -1};
int dir_col[4] = {1, -1, 0, 0};

// 从 (row, col) 出发继续走，每到达一次终点就找到一条完整路径。
void dfs(int row, int col) {
    if (row == end_row && col == end_col) {
        path_count += 1;  // 到达终点，统计当前这条路径
        return;
    }

    // 这一层枚举四个方向的下一步选择。
    for (int dir = 0; dir < 4; dir += 1) {
        int next_row = row + dir_row[dir];
        int next_col = col + dir_col[dir];
        if (next_row < 0 || next_row >= rows || next_col < 0 || next_col >= cols) {
            continue;  // 出界
        }
        if (blocked[next_row][next_col] || visited[next_row][next_col]) {
            continue;  // 障碍或已被当前路径走过
        }

        visited[next_row][next_col] = 1;  // 前进阶段：先标记下一格已访问
        dfs(next_row, next_col);
        visited[next_row][next_col] = 0;  // 回溯阶段：撤销标记，把格子还给其它分支
    }
}

int main() {
    std::cin >> rows >> cols >> obstacle_count;
    std::cin >> start_row >> start_col >> end_row >> end_col;
    // 输入是 1 起始坐标，数组内部统一转成 0 起始下标。
    start_row -= 1;
    start_col -= 1;
    end_row -= 1;
    end_col -= 1;

    for (int k = 0; k < obstacle_count; k += 1) {
        int x, y;
        std::cin >> x >> y;
        blocked[x - 1][y - 1] = 1;
    }

    visited[start_row][start_col] = 1;  // 起点视为已访问，防止路径绕回起点
    dfs(start_row, start_col);
    std::cout << path_count << '\n';
    return 0;
}

复杂度

时间：简单路径计数没有多项式做法，最坏枚举指数级路径，记为 $O(4^{nm})$ 。本题 $N, M \leqslant 5$ ，完全可行。
空间：两个 $O(nm)$ 的标记数组加上深度不超过 $nm$ 的递归栈，为 $O(nm)$ 。

总结

这道题是 DFS 回溯统计简单路径的标准模板：每层递归做一个方向选择，前进时标记、回溯时撤销，到达目标时计数。理解了「标记/撤销」为什么必须成对出现，就理解了回溯的本质；同时它也是 rbook《递归实现多重循环》「搜索树的基础模型」的经典例题。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14统计 N x M 网格中从起点到终点的简单路径条数
        |
        | 关键观察
        |   一条路径 = 一串「上下左右」的方向选择序列
        |   每个格子最多经过一次（简单路径约束）
        v
DFS 回溯（main.cpp）
   每层递归：枚举当前格子的 4 个方向选择
   前进阶段：vis[nx][ny] = 1 标记进入
   回溯阶段：vis[nx][ny] = 0 撤销标记
   到达终点：ans++ 统计一条完整路径
        |
        v
复杂度 O(4^(n*m))，空间 O(n*m)

图中从上到下是「模型 → 算法 → 复杂度」的推导链。关键在中间两步：路径被建模成方向选择序列，DFS 逐层枚举选择；vis 的标记与撤销必须成对出现，它把「当前路径已访问」和「曾经被其他路径访问过」严格区分开，这正是回溯能不重不漏统计全部简单路径的原因。

迷宫

目录

形式化题目

思路

代码

Guide 风格代码

复杂度

总结

图示解析