预处理每个传送门端点的另一端，BFS 进入字母格时立即跳转并只增加一次移动时间。
OJ: luogu
题目 ID: P1825
难度:普及/提高-
标签:BFS网格最短路python
日期: 2026-07-16 18:01
题意
在玉米迷宫中从 @ 到 =。移动到相邻格花一单位时间；踏上成对大写字母后必须立即免费传送到另一个同字母端点。
思路
先扫描迷宫，按字母把大写传送门坐标存进 vector（每字母恰好两个位置）。
BFS 尝试走入相邻格：若不是墙且未被访问过，就进一步判断——如果是大写字母，则从 vector 中找到同字母的另一端跳转过去，再入队；否则直接入队。无论是否触发传送，步数都只加一。
因为步数代价统一为 1，普通 BFS 就能求出最短路。
Python 知识
defaultdict(list)按字母收集两个端点。- 字典推导式配合
enumerate(pair)同时建立两个方向的映射。 cell.isupper()直接识别大写字母传送门。- 坐标元组可同时作为字典键、集合元素和队列状态。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：defaultdict、集合与deque。/home/rainboy/mycode/hugo-blog/content/program_language/python/bfs_shortest.md：网格最短路状态。
代码
python
from collections import defaultdict, deque
n, m = map(int, input().split())
maze = [input().strip() for _ in range(n)]
portals = defaultdict(list)
for x, row in enumerate(maze):
for y, cell in enumerate(row):
if cell == "@":
start = x, y
elif cell.isupper():
portals[cell].append((x, y))
other_end = {
point: pair[1 - index]
for pair in portals.values()
for index, point in enumerate(pair)
}
queue = deque([(*start, 0)])
visited = {start}
answer = -1
while queue:
x, y, distance = queue.popleft()
if maze[x][y] == "=":
answer = distance
break
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nxt = x + dx, y + dy
if not (0 <= nxt[0] < n and 0 <= nxt[1] < m):
continue
if maze[nxt[0]][nxt[1]] == "#":
continue
if nxt in other_end:
nxt = other_end[nxt]
if nxt not in visited:
visited.add(nxt)
queue.append((*nxt, distance + 1))
print(answer)cpp
/* author: Rainboy email: rainboylvx@qq.com time: 2022年 02月 13日 星期日 19:37:03 CST */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3+5,maxe = 1e3+5; //点与边的数量
/* 顺时针-4个方向 */
int fx[][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} };
int n,m;
// 判断 (x,y) 是否在迷宫范围内
bool in_mg(int x,int y){
return x >= 1 && x <=n && y >=0 && y<m;
}
// BFS 队列节点：x,y 为坐标，s 为起点到该点的最少步数
struct node {
int x,y,s;
};
bool vis[maxn][maxn]; // 访问标记
string mg[maxn]; // 迷宫，每行一个字符串
int sx,sy,tx,ty; // 起点 @，终点 =
vector<node> v[30]; // v[c] 存储所有大写字母 c 对应的传送门坐标（每字母恰好两个）
void init(){
std::cin >> n >> m;
for(int i=1;i<=n;++i){
std::cin >> mg[i];
for(int j=0;j<=m-1;++j){
if( mg[i][j] == '='){
tx = i;
ty = j;
}
else if(mg[i][j] == '@'){
sx = i;
sy = j;
}
else if(std::isupper(mg[i][j])){
v[mg[i][j] - 'A'].push_back({i,j,0}); // 记录传送门位置
}
}
}
}
// BFS 求最短路，遇到传送门立即跳到另一端
int bfs(){
queue<node> q;
q.push({sx,sy,0});
vis[sx][sy] = 1;
while ( !q.empty() ) {
node h = q.front();
q.pop();
if( h.x == tx && h.y == ty ) return h.s; // 到达终点
for(int i=0;i<=3;++i){
int nx = h.x + fx[i][0];
int ny = h.y + fx[i][1];
// 越界、撞墙、已访问 则跳过
if( !in_mg(nx, ny) || mg[nx][ny] == '#' || vis[nx][ny] ) continue;
if( isupper(mg[nx][ny])){ // 踩到传送门
int t = mg[nx][ny] - 'A';
vis[nx][ny] = 1;
// 找到同一字母的另一个传送门，跳转过去
for(int k = 0 ;k < v[t].size() ; ++k){
if( v[t][k].x != nx || v[t][k].y != ny ){
nx = v[t][k].x;
ny = v[t][k].y;
break;
}
}
q.push({nx,ny,h.s+1});
}
else { // 普通格子
q.push({nx,ny,h.s+1});
vis[nx][ny] = 1;
}
}
}
return -1; // 无法到达
}
int main(int argc,char * argv[]){
init();
int ans = bfs();
std::cout << ans << std::endl;
return 0;
}复杂度
预处理和 BFS 都至多扫描常数次网格，时间与空间复杂度均为
总结
免费传送不需要额外入队一层：在生成邻居时直接把端点规范成另一端，就能继续使用普通 BFS 的层数作为时间。