走迷宫

题意

$m \times n$ 迷宫，1 可走 0 不可走。给定起点和终点，找出所有可行道路，要求：

路径中不能重复经过同一个点；
只能上下左右四个方向；
优先顺序：上、左、右、下；
每条路径一行，用 (x,y)->(x,y)->... 输出；无路输出 $-1$ 。

数据范围： $1 < m, n < 15$ ，数据随机生成。

思路

最直接的想法是枚举所有路径：

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
68/**
 * 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-05 11:20
 * update_at: 2026-08-05 11:20
 */
// brute.cpp：小数据暴力解，用递归回溯枚举所有简单路径，
// 与 main.cpp 独立实现，方向顺序保持一致，用于交叉验证。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int m, n;
int mp[MAXN][MAXN];
int sx, sy, ex, ey;
bool vis[MAXN][MAXN];
vector<pair<int, int>> path;
bool has_ans;

int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};

void print_path() {
    for (size_t i = 0; i < path.size(); i++) {
        if (i) cout << "->";
        cout << "(" << path[i].first << "," << path[i].second << ")";
    }
    cout << '\n';
}

void dfs(int x, int y) {
    if (x == ex && y == ey) {
        has_ans = true;
        print_path();
        return;
    }
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > m || ny < 1 || ny > n) continue;
        if (mp[nx][ny] == 0 || vis[nx][ny]) continue;
        vis[nx][ny] = true;
        path.push_back({nx, ny});
        dfs(nx, ny);
        path.pop_back();
        vis[nx][ny] = false;
    }
}

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

    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> mp[i][j];
    cin >> sx >> sy >> ex >> ey;

    vis[sx][sy] = true;
    path.push_back({sx, sy});
    dfs(sx, sy);

    if (!has_ans) cout << -1 << '\n';

    return 0;
}

关键点：题目要输出所有路径，所以不能用 BFS（BFS 只找一条最短路径），必须用 DFS 回溯——每到达终点就输出当前路径，然后返回继续尝试其他分支。

DFS 结构：

text

1
2
3
4
5dfs(x, y)：当前在 (x, y)
  ├─ 到达终点 → 输出 path_x[0..path_len-1]
  └─ 按 上、左、右、下 顺序尝试四个方向
       ├─ 出界 / 是墙 / 已访问 → 跳过
       └─ 标记访问 → 记录路径 → dfs(nx, ny) → 回溯撤销

方向顺序为什么重要：题目要求按"上左下右"优先顺序输出路径。方向数组 dx = {-1, 0, 0, 1}, dy = {0, -1, 1, 0} 严格对应这个顺序，DFS 按这个顺序尝试，输出自然就是题目要求的顺序。

以样例第一条路径为例，从 $(1,1)$ 出发：上、左出界，右 $(1,2)$ 是 0 不可走，只能下到 $(2,1)$ ，这正是样例输出的第一条：

text

1(1,1)->(2,1)->(2,2)->...->(5,6)

代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * 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-05 11:20
 * update_at: 2026-08-29 16:59
 */
// DFS 枚举所有简单路径：路径上不能重复经过点，方向按 左、上、右、下 顺序尝试。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int m, n;               // m 行 n 列
int mp[MAXN][MAXN];     // 1 可走，0 不可走
int sx, sy, ex, ey;     // 起点、终点
bool vis[MAXN][MAXN];   // 当前路径上是否已走过
int path_x[MAXN * MAXN], path_y[MAXN * MAXN];   // 路径上的点
int path_len;           // 当前路径长度
bool has_ans;           // 是否至少找到一条路径

int dx[4] = {0, -1, 0, 1};    // 左 上 右 下
int dy[4] = {-1, 0, 1, 0};

void print_path() {
    for (int i = 0; i < path_len; i++) {
        if (i) cout << "->";
        cout << "(" << path_x[i] << "," << path_y[i] << ")";
    }
    cout << '\n';
}

// 当前在 (x, y)，尝试走到终点
void dfs(int x, int y) {
    if (x == ex && y == ey) {   // 到达终点，输出当前完整路径
        has_ans = true;
        print_path();
        return;
    }

    for (int k = 0; k < 4; k++) {   // 按 左上右下 顺序尝试
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > m || ny < 1 || ny > n) continue;   // 出界
        if (mp[nx][ny] == 0) continue;                        // 不可走
        if (vis[nx][ny]) continue;                            // 路径不能重复

        vis[nx][ny] = true;
        path_x[path_len] = nx;
        path_y[path_len] = ny;
        path_len++;

        dfs(nx, ny);

        path_len--;              // 回溯：撤销这一步
        vis[nx][ny] = false;
    }
}

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

    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> mp[i][j];
    cin >> sx >> sy >> ex >> ey;

    if (mp[sx][sy] == 0 || mp[ex][ey] == 0) {
        cout << -1 << '\n';
        return 0;
    }

    vis[sx][sy] = true;
    path_x[0] = sx;
    path_y[0] = sy;
    path_len = 1;

    dfs(sx, sy);

    if (!has_ans) cout << -1 << '\n';

    return 0;
}

复杂度

$m, n < 15$ ，简单路径数量由数据决定（全 1 时指数级），DFS 对每条路径输出一次。空间 $O(m \cdot n)$ （路径长度不超过格子数）。

总结

输出所有方案 → DFS 回溯；
输出最短方案 → BFS；
路径不重复点 → vis 标记，回溯时撤销；
方向顺序敏感的输出 → 方向数组严格按题意排列。

图示解析

text

1
2
3(1,1)→(2,1)→(2,2)→(2,3)→(2,4)→(2,5)→(3,5)→(3,4)→(3,3)
                                                    │
(5,6)←(5,5)←(4,5)←(4,4)←(4,3)←──────────────────────┘

读图方法：这是样例第一条路径（上左下右顺序下的第一条）。注意路径会绕行（如 $(2,4)$ 到 $(3,3)$ 一段），因为 DFS 会尝试所有合法分支，只要不重复经过点即可。

目录

题意

思路

代码

复杂度

总结

图示解析