P1825 [USACO11OPEN] Corn Maze S
题解：
用广度优先搜索（BFS）。每次从队列取出当前格子，向四个方向尝试：
如果是墙或越界，跳过；
如果是普通格子且未访问，标记距离/访问并入队；
如果是大写字母，找到同字母的另一个端点（传送终点），把传送终点当作下一步入队（并标记已访问/距离）。
注意，这里不把“传送起点格”本身标记为已访问，而是把传送的目标端点标记为访问/距离。
这题题目描述有问题：
我最开始认为传送后就只能移动到普通草地，然后才能再次传送。
不过，题目中的描述是防止在两个 A 间反复横跳。
从一个 A 传送到另一个 A ，然后移动到 B ，这一步也算移动，所以 **可以立即使用 B **
比如下面这个用例：
6 7
#=#####
#ABCDE#
#ABCDE#
#ZXYV.#
#VYXZ@#
#######
走的路线是Z -> A -> 目的地=， 只需要3步
代码如下：
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=310;
const int INF = 1e9;
int n, m;
char a[N][N];
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, 1, -1};
int sx, sy, ex, ey;
// 记录每个大写字母的两个端点
vector<tuple<int,int>> pos[26];
int dista[N][N];//记录距离，同时起到vis[]去重的作用int main()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){char c; cin>>c;a[i][j]=c;if(c=='@') sx=i, sy=j;else if(c=='=') ex=i, ey=j;else if(isupper(c)){pos[c - 'A'].push_back({i, j});}}// 初始化距离for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)dista[i][j] = INF; queue<tuple<int, int>> q;dista[sx][sy]=0;q.push({sx, sy}); while(!q.empty()){auto [x, y] = q.front(); q.pop();// printf("%c %d %d %d\n", a[x][y], x, y, dista[x][y]);if(a[x][y] == '=') { cout<<dista[x][y];exit(0);}for(int i=0;i<4;i++){int nx = x + dx[i];int ny = y + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m) continue;if (a[nx][ny] == '#') continue;//滑梯if(isupper(a[nx][ny])){int id = a[nx][ny] - 'A';// 找到另一个端点for (auto [xx, yy] : pos[id]) {if (xx != nx || yy != ny) {if(dista[xx][yy]!=INF) continue;//另一端已访问dista[xx][yy]=dista[x][y]+1;//只需要标记另一端q.push({xx, yy});// printf("a[nx][ny] %c %d %d %d ——> %d %d %d\n",a[nx][ny], nx, ny, dista[x][y], xx, yy, dista[xx][yy]);}}} //草地else{if(dista[nx][ny]!=INF) continue;//已访问dista[nx][ny]=dista[x][y]+1;q.push({nx, ny});}}}cout<<-1<<"\n";return 0;
}