迷宫 - 题目列表

题意

在最多 5x5 的网格中，从起点上下左右移动到终点。障碍不能进入，每个格子最多经过一次，统计不同路径数量。

思路

网格很小，可以直接 DFS 枚举路径。到达终点时当前选择序列形成一条合法路径，返回 1；否则尝试四个方向，把所有子问题返回的路径数相加。

进入下一格前加入 visited，递归返回后删除。这一步撤销非常重要，否则当前分支访问过的格子会错误地阻止其他路径使用。

Python 知识

坐标写成 (x,y) 元组，可直接放入 blocked 和 visited 集合。
routes += dfs(*nxt) 用 * 把坐标元组解包成两个参数。
set.add 与 set.remove 对应回溯的选择和撤销。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：DFS 回溯与状态恢复。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：元组状态与集合判重。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24n, m, obstacle_count = map(int, input().split())
start_x, start_y, finish_x, finish_y = map(int, input().split())
blocked = {tuple(map(int, input().split())) for _ in range(obstacle_count)}
visited = {(start_x, start_y)}


def dfs(x, y):
    if (x, y) == (finish_x, finish_y):
        return 1

    routes = 0
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nxt = x + dx, y + dy
        if not (1 <= nxt[0] <= n and 1 <= nxt[1] <= m):
            continue
        if nxt in blocked or nxt in visited:
            continue
        visited.add(nxt)
        routes += dfs(*nxt)
        visited.remove(nxt)
    return routes


print(dfs(start_x, start_y))

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P1605 迷宫 */
/* DFS 回溯统计从起点到终点的所有简单路径数量。 */

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

const int MAXN = 10;

int n, m, obs_cnt;
int sx, sy, fx, fy; // 起点和终点
int vis[MAXN][MAXN]; // 0 可走，1 障碍物或已访问
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int ans;

// 从 (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 (vis[nx][ny]) continue;

        vis[nx][ny] = 1;  // 标记已访问
        dfs(nx, ny);
        vis[nx][ny] = 0;  // 回溯撤销
    }
}

int main() {
    cin >> n >> m >> obs_cnt;
    cin >> sx >> sy >> fx >> fy;

    for (int i = 1; i <= obs_cnt; i++) {
        int x, y;
        cin >> x >> y;
        vis[x][y] = 1; // 障碍物
    }

    vis[sx][sy] = 1; // 起点标记
    dfs(sx, sy);
    cout << ans << "\n";
    return 0;
}

复杂度

最坏需要枚举指数级简单路径，可粗略记为 $O(4^{nm})$ ；递归栈和访问集合为 $O(nm)$ 。

总结

这题不是求最短路，而是统计所有不重复经过格子的路径，因此必须用回溯，在每个分支结束后恢复访问状态。

迷宫

目录

题意

思路

Python 知识

代码

复杂度

总结