献给阿尔吉侬的花束

形式化题目

给定一个 $R \times C$ 的网格，每个格子为空地 .、墙壁 #、起点 S 或终点 E（各恰好一个）。从 S 出发，每步可移动到上下左右相邻的非墙壁格子，求到达 E 的最少步数。若不可达，输出特定字符串。

思路

本题是典型的无权网格图单源最短路问题。因为每步代价均为 1，广度优先搜索（BFS）天然按层扩展，第一次访问到终点时的层数即为最短距离。

算法流程

扫描网格，记录起点 S 和终点 E 的坐标
初始化距离数组 dist 为 -1（表示未访问），dist[S] = 0，将 S 入队
队列非空时循环：
- 弹出队首 (x, y)
- 若已到达 E，可提前结束
- 向上下左右四个方向扩展：
  - 越界、撞墙、已访问则跳过
  - 否则 dist[nx][ny] = dist[x][y] + 1，入队
循环结束后，dist[E] 即为答案；若为 -1 则输出 oop!

关键点

dist 数组既存距离又作访问标记，避免重复入队
四向偏移用 dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1} 简化代码
多测试用例独立处理，变量在循环内重新初始化

BFS 扩展过程示意（以样例 1 为例）

样例 1 网格：

text

1
2
3.S..
###.
..E.

BFS 层序扩展距离数组变化（- 表示未访问/墙壁）：

步骤	队首	dist 状态（仅显示可达区域）
0	(0,1)	`S`:0
1	(0,1)	(0,0):1, (0,2):1, (1,1):1
2	(0,0)	(1,0):2
3	(0,2)	(0,3):2, (1,2):2
4	(1,1)	已访问
5	(1,0)	(2,0):3
6	(0,3)	(1,3):3
7	(1,2)	(2,2):3 ← 终点 `E`，距离 3+2=5

从表中可见，终点 E 第一次被赋值为 5，即为最短步数。

代码

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/**
 * 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-09-05 11:08
 */
// 用固定数组和 std::queue 做多组网格 BFS，求 S 到 E 的最短步数。
#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 205;

struct Point {
    int x, y;
};

int R, C;                   // 当前这组数据的地图大小 R 行 C 列
char grid[MAXN][MAXN];      // 迷宫地图
int dist[MAXN][MAXN];       // dist[i][j] 表示从 S 走到 (i,j) 的最短步数, -1 表示还没走到
int sx, sy, ex, ey;         // 起点 S 与终点 E 的坐标

int dx[4] = {-1, 1, 0, 0}; // 上、下、左、右四个方向的行偏移
int dy[4] = {0, 0, -1, 1}; // 上、下、左、右四个方向的列偏移

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

    int T; // 一共有 T 组数据
    cin >> T;

    while (T--) {
        cin >> R >> C;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                cin >> grid[i][j];
                dist[i][j] = -1; // 每组数据开始时全部标记为未到达

                if (grid[i][j] == 'S') { // 记录起点
                    sx = i;
                    sy = j;
                }
                if (grid[i][j] == 'E') { // 记录终点
                    ex = i;
                    ey = j;
                }
            }
        }

        std::queue<Point> q; // BFS 队列, 存等待扩展的格子
        dist[sx][sy] = 0;    // 起点步数为 0
        q.push({sx, sy});

        while (!q.empty()) {
            Point now = q.front();
            q.pop();

            // BFS 按层扩展, 第一次遇到终点时步数已经最小, 可以提前结束
            if (now.x == ex && now.y == ey) break;

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

                if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // 越界
                if (grid[nx][ny] == '#') continue;                    // 墙壁不可走
                if (dist[nx][ny] != -1) continue;                     // 已经到达过, 不再入队

                dist[nx][ny] = dist[now.x][now.y] + 1; // 从当前格多走一步
                q.push({nx, ny});
            }
        }

        if (dist[ex][ey] == -1) cout << "oop!\n"; // 终点始终没被访问, 不可达
        else cout << dist[ex][ey] << '\n';        // 输出最短步数
    }

    return 0;
}

另一种队列实现的写法,把每组数据的处理拆成 init() 与 bfs() 两个函数:

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/**
 * 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-09-05 11:01
 * update_at: 2026-09-05 11:12
 */
// main2.cpp：字符迷宫 BFS（多组数据），使用 std::queue 实现队列。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int R, C;                 // 当前这组数据的迷宫大小: R 行 C 列
char maze[MAXN][MAXN];    // 迷宫地图, '#' 表示墙, '.' 表示空地
int dis[MAXN][MAXN];      // dis[x][y] 表示从 S 到 (x,y) 的最短步数, -1 表示没走到过
int sx, sy, tx, ty;       // 起点 S 和终点 E 的坐标

// 队列中的元素: 一个格子的坐标
struct node {
    int x, y;
};

int dx[] = {-1, 1, 0, 0}; // 上、下、左、右四个方向的行偏移
int dy[] = {0, 0, -1, 1}; // 上、下、左、右四个方向的列偏移

// 读入一组数据, 同时记录起点和终点的坐标
void init() {
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> maze[i][j];
            dis[i][j] = -1; // 每组开始时全部标记为未到达

            if (maze[i][j] == 'S') { // 记录起点
                sx = i;
                sy = j;
            }
            if (maze[i][j] == 'E') { // 记录终点
                tx = i;
                ty = j;
            }
        }
    }
}

// 从 (x,y) 出发 BFS, 把能到达的每个格子的最短步数写进 dis
void bfs(int x, int y) {
    queue<node> q; // BFS 队列, 存等待扩展的格子
    dis[x][y] = 0; // 起点步数为 0
    q.push({x, y});

    while (!q.empty()) {
        node h = q.front();
        q.pop();

        // 枚举上下左右四个方向
        for (int i = 0; i < 4; i++) {
            int nx = h.x + dx[i];
            int ny = h.y + dy[i];

            if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // 出界
            if (maze[nx][ny] == '#') continue;                    // 墙
            if (dis[nx][ny] != -1) continue;                      // 已经访问过

            dis[nx][ny] = dis[h.x][h.y] + 1; // 从当前格多走一步
            q.push({nx, ny});
        }
    }
}

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

    int T; // 一共有 T 组数据
    cin >> T;

    while (T--) {
        init();
        bfs(sx, sy); // 从起点开始 BFS

        // dis[终点] != -1 说明终点可达, 输出最短步数
        if (dis[tx][ty] != -1) {
            cout << dis[tx][ty] << '\n';
        } else {
            cout << "oop!\n";
        }
    }

    return 0;
}

复杂度

时间复杂度： $O(T \cdot R \cdot C)$ 。每个格子最多入队出队一次，四向扩展为常数操作。 $T \le 10, R,C \le 200$ ，总操作数 $\le 4 \times 10^5$ 。
空间复杂度： $O(R \cdot C)$ 。存网格、距离数组、队列，均为 $R \times C$ 级别。

总结

本题考察网格 BFS 基础模板。核心在于：

识别无权图最短路 = BFS 层数
dist 初始化为 -1 兼作访问标记
四向扩展的边界与合法性检查

此类题目是图论入门必刷模板，熟练掌握后可直接套用到迷宫、矩阵最短路、多源 BFS 等变种中。

图示解析

BFS 层序扩展示意图

这张图展示从起点 S 开始，BFS 如何一层层向外扩展，直到到达终点 E：

flowchart TD
    S((S:0)) --> A((0,0):1)
    S --> B((0,2):1)
    S --> C((1,1):1)
    A --> D((1,0):2)
    B --> E((0,3):2)
    B --> F((1,2):2)
    D --> G((2,0):3)
    E --> H((1,3):3)
    F --> I((2,2):3)
    I --> E点((2,2):5)

    classDef start fill:#90EE90;
    classDef end fill:#FFB6C1;
    classDef wall fill:#D3D3D3;
    class S start;
    class E点 end;

从图中可以看到：

BFS 按距离递增顺序访问节点，第 k 层的所有节点距离起点均为 k
终点 E 第一次被访问时（距离 5），路径必然是最短的
墙壁 # 自然阻断了扩展方向，不需要特殊处理