[USACO11OPEN] Corn Maze S

形式化题目

有一个 $n \times m$ 的网格迷宫，格子分为墙、草地、起点与出口四类；另有若干对传送门，每对用同一个大写字母标记，同一字母恰好出现两次。从起点出发，每次可以移动到相邻的草地格，花费 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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125/**
 * 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:33
 * update_at: 2026-08-13 13:33
 */
// brute.cpp：小数据暴力解。把每个格子看成一个点，把每个合法移动建成一条
// 代价为 1 的有向边（走入传送门端点时直接连到配对端点），在显式图上跑普通 BFS。
// 与 main.cpp"展开邻居时内联瞬移"的写法相互独立，用来辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;
const int MAXV = 305 * 305 + 5;

int n, m;
char maze[MAXN][MAXN];      // 迷宫
int sx, sy, ex, ey;         // 起点 @ 与终点 =

int cnt[26];                // 每个大写字母出现的次数
int px[26][2], py[26][2];   // 每个大写字母两个端点的坐标

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

vector<int> g[MAXV];        // 显式图：g[id] 存放从该点走一步能到达的点
int dist[MAXV];             // dist[id] 起点到该点的最少步数，-1 表示未访问

// 把坐标 (x,y) 映射成图上的点编号
int id(int x, int y) {
    return x * m + y;
}

// 读入迷宫，记录起点、终点和传送门端点
void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> (maze[i] + 1);
        for (int j = 1; j <= m; j++) {
            if (maze[i][j] == '@') {
                sx = i;
                sy = j;
            } else if (maze[i][j] == '=') {
                ex = i;
                ey = j;
            } else if (maze[i][j] >= 'A' && maze[i][j] <= 'Z') {
                int c = maze[i][j] - 'A';
                px[c][cnt[c]] = i;
                py[c][cnt[c]] = j;
                cnt[c]++;
            }
        }
    }
}

// 显式建图：从每个格子向"走一步能到达的格子"连一条 1 权边
void build_graph() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (maze[i][j] == '#') continue;

            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];

                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                if (maze[nx][ny] == '#') continue;

                if (maze[nx][ny] >= 'A' && maze[nx][ny] <= 'Z') {
                    // 走入传送门端点：必须瞬移到配对端点，瞬移免费，所以仍是 1 权边
                    int c = maze[nx][ny] - 'A';
                    int ox = px[c][0], oy = py[c][0];
                    if (ox == nx && oy == ny) {
                        ox = px[c][1];
                        oy = py[c][1];
                    }
                    g[id(i, j)].push_back(id(ox, oy));
                } else {
                    g[id(i, j)].push_back(id(nx, ny));
                }
            }
        }
    }
}

// 普通 BFS 求最短路
int bfs() {
    queue<int> q;
    memset(dist, -1, sizeof(dist));

    int s = id(sx, sy);
    int t = id(ex, ey);
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == t) {
            return dist[u];
        }

        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return -1; // 终点不可达
}

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

    read_input();
    build_graph();
    cout << bfs() << '\n';

    return 0;
}

brute.cpp 把题意直接翻译成图：每个格子一个点，"走入传送门端点"被建成一条直达配对端点的 1 权有向边，然后跑普通 BFS。它正确、容易逐条对照题意，但对本题而言把整张邻接表建出来是多余的。

关键观察有三点：

走入端点必须瞬移：移动目标是端点时，落点直接变成配对端点，不存在"停在端点上"的状态；
瞬移恰好一次即可：配对端点同字母，若瞬移后再判定传送门会跳回原端点，在两个端点间无限往返；
瞬移免费：整个"走一步 + 瞬移"仍然只花 1 时间，所有边的有效代价都是 1，普通 BFS 的层数就是步数。

于是正式解是内联瞬移的 BFS（main.cpp）：预处理扫描迷宫，收集每个大写字母的两个端点，建立"端点 → 配对端点"的映射表；BFS 展开邻居时，若目标是端点就先替换成配对端点，再判重入队，步数照常加 1。

样例走法

这张图把样例的最优路径画成状态序列，重点看第 1 步的瞬移：

text

1@(4,3) 步数0 --第1步 走1步--> W(4,4) ==瞬移0步(第1步内)==> W(2,3) --第2步 走1步--> .(2,4) --第3步 走1步--> =(1,4)

观察要点：第 1 步从 @ 向右走入 W 端点，落点不是 (4,4) 而是配对端点 (2,3)，但这一步仍然只算 1 步（瞬移免费）；到达 (2,3) 后端点本身可以停留，第 2、3 步是普通移动。全程 3 步，与样例输出一致。

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125/**
 * 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:33
 * update_at: 2026-08-13 13:35
 */
// main.cpp：P1825 Corn Maze S 正式解。BFS 求最短路，
// 走入传送门端点时在展开邻居的同一层内立即瞬移到配对端点。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;
const int MAXM = 305;

int n, m;
char maze[MAXN][MAXM];      // 迷宫，maze[i][j] 是 (i,j) 上的字符
int dist[MAXN][MAXM];       // dist[i][j] 起点到 (i,j) 的最少步数，-1 表示未访问

int sx, sy;                 // 起点 @ 的坐标
int ex, ey;                 // 终点 = 的坐标

int to_x[MAXN][MAXM];       // (i,j) 是传送门端点时，配对端点的横坐标，否则为 -1
int to_y[MAXN][MAXM];       // 配对端点的纵坐标

int cnt[26];                // cnt[c] 大写字母 c 出现的次数（每个字母恰好 2 次）
int px[26][2], py[26][2];   // 每个大写字母两个端点的坐标

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

// 判断 (x,y) 是否在迷宫范围内
bool in_maze(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

void read_input() {
    cin >> n >> m;
    memset(to_x, -1, sizeof(to_x));
    memset(to_y, -1, sizeof(to_y));

    for (int i = 1; i <= n; i++) {
        cin >> (maze[i] + 1);
        for (int j = 1; j <= m; j++) {
            if (maze[i][j] == '@') {
                sx = i;
                sy = j;
            } else if (maze[i][j] == '=') {
                ex = i;
                ey = j;
            } else if (maze[i][j] >= 'A' && maze[i][j] <= 'Z') {
                int c = maze[i][j] - 'A';
                px[c][cnt[c]] = i;
                py[c][cnt[c]] = j;
                cnt[c]++;
            }
        }
    }

    // 每个字母恰好两个端点，把它们互相记录为对方的配对端点
    for (int c = 0; c < 26; c++) {
        if (cnt[c] == 2) {
            int x1 = px[c][0], y1 = py[c][0];
            int x2 = px[c][1], y2 = py[c][1];
            to_x[x1][y1] = x2;
            to_y[x1][y1] = y2;
            to_x[x2][y2] = x1;
            to_y[x2][y2] = y1;
        }
    }
}

// BFS 求最短步数：移动一格计 1 步；走入传送门端点必须瞬移，瞬移免费，
// 所以"走一步 + 瞬移"整体仍只计 1 步。
int bfs() {
    queue<pair<int, int>> q;
    memset(dist, -1, sizeof(dist));

    dist[sx][sy] = 0;
    q.push(make_pair(sx, sy));

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (x == ex && y == ey) {
            return dist[x][y];
        }

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (!in_maze(nx, ny) || maze[nx][ny] == '#') continue;

            // 走入的是传送门端点：必须瞬移到配对端点。
            // 配对端点与当前端点同字母，瞬移恰好一次即完成；
            // 若瞬移后再次检查传送门，就会在两个端点之间来回跳，形成死循环。
            if (to_x[nx][ny] != -1) {
                // 先保存配对端点坐标再赋值，避免修改 nx 后 to_y 下标错位
                int tx = to_x[nx][ny];
                int ty = to_y[nx][ny];
                nx = tx;
                ny = ty;
            }

            if (dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
    return -1; // 终点不可达
}

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

    read_input();
    cout << bfs() << '\n';

    return 0;
}

复杂度

时间：预处理与 BFS 都只扫常数次网格， $O(nm)$ 。
空间：迷宫、配对表、步数表各 $O(nm)$ ，总空间 $O(nm)$ 。

总结

传送门没有引入新的代价：把"走一步 + 瞬移"整体看成一条代价 1 的边，问题就和普通网格最短路一样，普通 BFS 即可。实现上只需注意两点：走入端点必须替换成配对端点（只替换一次，防止端点间死循环）；替换前先保存配对坐标再赋值。BFS 基础可参考 rbook《图的遍历》。

图示解析

这张 ASCII 图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6
7
8网格迷宫 @ 到 =（每对同字母传送门 A-Z，双向免费）
`- 关键观察 1：走入传送门端点必须立即瞬移到配对端点，不能停留在端点
   `- 关键观察 2：配对端点同字母，瞬移恰好一次即可，二次瞬移会来回死循环
      `- 关键观察 3：瞬移免费，所以"走一步 + 瞬移"整体代价仍是 1
         `- 选择算法：普通 BFS（所有边代价 1，层数即步数）
            |- 预处理：扫描迷宫，记录每字母两个端点，建立 to_x/to_y 配对表
            |- 展开邻居：若邻居是端点，先替换成配对端点再判重入队
            `- 首次到达终点时的 dist 就是答案

顺着箭头看，三条关键观察依次排除了"额外建图"“多次瞬移”"分层入队"三种绕路做法，最终落点是"与普通网格最短路几乎相同"的 BFS，预处理与遍历都只扫常数次网格。