[语言月赛 202508] 迷宫寻路

题意

$n \times m$ 的数字迷宫，每个格子写有 $1 \sim 4$ （1 上 2 下 3 左 4 右）。人在格子上就按该格数字移动一步，直到走出迷宫。

$q$ 次询问，每次给起点，回答需要多少步离开迷宫；永远走不出输出 $-1$ 。

数据范围： $1 \leqslant n, m, q \leqslant 100$ 。

思路

最直接的想法是每个询问一步步模拟，重复访问某个格子就说明进入了环：

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/**
 * 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:10
 * update_at: 2026-08-05 11:10
 */
// brute.cpp：小数据暴力解，对每个询问直接一步步模拟移动，
// 用 vis 时间戳判断是否进入环（重复访问同一格子）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m, q;
int a[MAXN][MAXN];
int vis[MAXN][MAXN];   // 本次模拟中是否访问过

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

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    for (int t = 0; t < q; t++) {
        int x, y;
        cin >> x >> y;
        memset(vis, 0, sizeof(vis));

        int step = 0;
        while (true) {
            if (x < 1 || x > n || y < 1 || y > m) {   // 离开迷宫
                cout << step << '\n';
                break;
            }
            if (vis[x][y]) {   // 重复访问：进入环，永远出不去
                cout << -1 << '\n';
                break;
            }
            vis[x][y] = 1;
            if (a[x][y] == 1) x--;
            else if (a[x][y] == 2) x++;
            else if (a[x][y] == 3) y--;
            else y++;
            step++;
        }
    }

    return 0;
}

这个暴力正确，但每个询问最多走 $n \times m$ 步， $q$ 次询问是 $O(q \cdot n \cdot m)$ 。虽然本题数据能过，但它没有利用一个关键性质。

关键观察：每个格子只有一个确定的去向。整个迷宫是一张每个节点出度恰好为 1 的有向图（函数图）：

从任意起点出发，路线唯一：要么走出迷宫，要么进入一个环；
同一个格子出发的答案固定，可以记忆化，无需重复计算。

用三色标记 DFS（ $f[x][y]$ ：0 未访问、 $-2$ 在递归栈中、 $-1$ 走不出、正数步数）一次计算所有格子的答案：

text

1
2
3
4当前格子 (x,y)
  ├─ 下一格出界      → 0 步（已经离开）
  ├─ 下一格在栈中    → -1（成环，永远出不去）
  └─ 下一格已算出    → 直接复用，+1 步

以样例第 1 组（起点 $(2,3)$ ）为例，路径为 $(2,3) \xrightarrow{2} (3,3) \xrightarrow{4} (3,4) \xrightarrow{1} (2,4) \xrightarrow{1} (1,4) \xrightarrow{4}$ 出界，共 5 步；起点 $(1,3)$ 方向 3 向左，绕一圈回到已访问格子，进入环，输出 $-1$ 。

代码

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/**
 * 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:10
 * update_at: 2026-08-05 11:10
 */
// 记忆化搜索：从每个格子出发只有一条固定路线（出度为 1 的函数图），
// 用三色标记 DFS 记录每个格子的答案，遇到栈中节点即进入环。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m, q;
int a[MAXN][MAXN];        // 1 上 2 下 3 左 4 右
int f[MAXN][MAXN];        // 0 未访问，-2 在递归栈中，-1 走不出，>0 步数

// 返回从 (x, y) 出发离开迷宫需要的步数；永远走不出返回 -1
int dfs(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m) return 0;   // 已经离开迷宫
    if (f[x][y] == -2) return -1;                      // 回到栈中节点：成环
    if (f[x][y] != 0) return f[x][y];                  // 已算出答案（含 -1）

    f[x][y] = -2;   // 标记当前节点在递归栈中

    int nx = x, ny = y;
    if (a[x][y] == 1) nx--;
    else if (a[x][y] == 2) nx++;
    else if (a[x][y] == 3) ny--;
    else ny++;

    int res = dfs(nx, ny);
    f[x][y] = (res == -1) ? -1 : res + 1;
    return f[x][y];
}

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

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    for (int t = 0; t < q; t++) {
        int x, y;
        cin >> x >> y;
        cout << dfs(x, y) << '\n';
    }

    return 0;
}

复杂度

每个格子至多被 DFS 访问一次，时间 $O(n \cdot m + q)$ ；空间 $O(n \cdot m)$ 。

总结

"每个节点只有一个去向"是函数图的关键特征。遇到这类问题：

路线唯一，可记忆化；
三色标记（未访问 / 栈中 / 已完成）可以一次 DFS 同时完成判环和计数。

图示解析

text

1
2
3
4
5
6
7数字迷宫（样例）          函数图视角
1 2 3 4                 每个格子只有一条出边
4 3 2 1
2 3 4 1

从 (2,3)=2 向下:         (2,3)→(3,3)→(3,4)→(2,4)→(1,4)→出界 = 5 步
从 (1,3)=3 向左:         (1,3)→(1,2)→(2,2)→(2,1)→(2,2) 进入环 → -1

读图方法：沿着箭头走，每格只有一个下一步。走出边界计步数；绕回已走过的格子就永远出不去。

[语言月赛 202508] 迷宫寻路

目录

题意

思路

代码

复杂度

总结

图示解析