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;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。