【题目来源】
洛谷：[P1825 USACO11OPEN] Corn Maze S - 洛谷
【题目描述】
去年秋天，农夫约翰带着奶牛们参观了一个玉米迷宫。但这不是一个普通的玉米迷宫：它有几个重力驱动的传送滑梯，可以让奶牛瞬间从迷宫中的一个点传送到另一个点。滑梯是双向的：奶牛可以瞬间从滑梯的起点滑到终点，或者从终点滑到起点。如果奶牛踩到滑梯的任一端，她必须使用滑梯。
传送操作不能连续使用，即，传送一次之后，必须通过非传送方式移动至少一步才能再次进行传送。
玉米迷宫的外部完全由玉米包围，只有一个出口。
迷宫可以用一个 \(N \times M\)（\(2 \leq N \leq 300\)；\(2 \leq M \leq 300\)）的网格表示。每个网格元素包含以下项目之一：
- 玉米（玉米网格元素不可通行）
- 草地（容易通过！）
- 滑梯端点（会将奶牛传送到另一个端点）
- 出口
奶牛只能从一个空间移动到相邻的下一个空间，前提是它们相邻且都不包含玉米。每个草地空间有四个潜在的邻居可以让奶牛到达。从一个草地空间移动到相邻空间需要 \(1\) 个时间单位；从一个滑梯端点移动到另一个端点需要 \(0\) 个时间单位。
填满玉米的空间用井号（#）表示。草地空间用英文句号（.）表示。滑梯端点对用相同的大写字母（A 到 Z）表示，并且没有两个不同的滑梯端点用相同的字母表示。出口用等号（=）表示。
贝茜迷路了。她知道自己在网格中的位置，并用「at」符号（@）标记了她当前的草地空间。她需要的最短时间是多少才能移动到出口空间？
【输入】
第一行：两个用空格隔开的整数 \(N\) 和 \(M\)。
第 \(2 \sim N+1\) 行：第 \(i+1\) 行描述了迷宫中的第 \(i\) 行的情况（共有 \(M\) 个字符，每个字符之间没有空格）。
【输出】
一个整数，表示起点到出口所需的最短时间。
【输入样例】
5 6
###=##
#.W.##
#.####
#.@W##
######
【输出样例】
3
【解题思路】
【算法标签】
《洛谷 P1825 Corn Maze》 #模拟# #搜索# #广度优先搜索,BFS# #最短路# #USACO# #2011#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n, m; // 地图的行数和列数
// 四个方向的偏移量：上、下、左、右
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
char a[305][305]; // 存储地图
char tmp; // 临时字符变量// 定义位置结构体，包含坐标和步数
struct node
{int x, y, step;
};// 定义传送门结构体，记录两个端点的坐标
struct mark
{int x1, y1, x2, y2;
} cs[100]; // 最多26个字母的传送门int main()
{// 输入地图尺寸cin >> n >> m;// 初始化BFS队列queue<node> q;// 读取地图数据for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];tmp = a[i][j];// 如果是传送门（A-Z）if (tmp >= 'A' && tmp <= 'Z') {// 记录传送门的两个端点if (cs[tmp].x1 == 0) {cs[tmp].x1 = i;cs[tmp].y1 = j;} else {cs[tmp].x2 = i;cs[tmp].y2 = j;}}// 如果是起点if (tmp == '@') {node tp = {i, j, 0}; // 初始步数为0q.push(tp);a[i][j] = '#'; // 标记为已访问}}}// BFS主循环while (!q.empty()) {node tp = q.front(); q.pop();// 尝试四个方向移动for (int i = 0; i < 4; i++) {int xx = tp.x + dx[i];int yy = tp.y + dy[i];// 检查边界if (xx < 1 || xx > n || yy < 1 || yy > m) continue;// 如果是障碍物if (a[xx][yy] == '#') continue;// 如果是可通行的空地if (a[xx][yy] == '.') {node t = {xx, yy, tp.step + 1};q.push(t);a[xx][yy] = '#'; // 标记为已访问continue;}// 如果是终点if (a[xx][yy] == '=') {cout << tp.step + 1; // 输出步数return 0;}// 如果是传送门if (cs[a[xx][yy]].x1 == xx && cs[a[xx][yy]].y1 == yy) {// 传送到另一端node t = {cs[a[xx][yy]].x2, cs[a[xx][yy]].y2, tp.step + 1};q.push(t);} else {// 传送到另一端node t = {cs[a[xx][yy]].x1, cs[a[xx][yy]].y1, tp.step + 1};q.push(t);}}}return 0;
}
【运行结果】
5 6
###=##
#.W.##
#.####
#.@W##
######
3