迷宫传送[最短路径]
问题描述
有一个由 H 行、W 列的网格组成的迷宫。用 (i, j) 表示从上往下第 i 行、从左往右第 j 列的格子。
每个格子 (i, j) 的类型由一个字符 S(i, j) 给出，其含义如下：
'.' ：空单元格
'#' ：障碍单元格
小写英文字母 (a–z) ：传送单元格
在迷宫中，你可以按任意顺序执行以下两种动作，次数不限：
行走：从当前单元格移动到相邻的上、下、左、右单元格之一。但不能移动到障碍格或网格外。
传送：当你位于传送单元格时，可以移动到相同字母的任意传送单元格。
请判断能否从单元格 (1,1) 移动到单元格 (H,W) 。如果可能，请输出所需的最小总动作次数；否则输出 -1。
约束条件
1 ≤ H, W ≤ 1000
H × W ≥ 2
H, W 为整数
S(i, j) 是 '.'、'#' 或小写英文字母
S(1,1) ≠ '#'
S(H,W) ≠ '#'
输入格式
H W S(1,1) S(1,2) … S(1,W) … S(H,1) S(H,2) … S(H,W)输出格式
如果可以从 (1,1) 移动到 (H,W)，则输出所需的最小总动作数；否则输出 -1。
问题分析
这是一个在网格中寻找从起点(1,1)到终点(H,W)最短路径的问题，但有一个特殊机制：传送。当站在某个字母格子上时，可以瞬间传送到所有相同字母的格子上。这相当于在图中添加了大量"快捷边"。
核心思路
1. 图模型转换
每个格子是一个节点
相邻格子（上下左右）之间有一条无向边（代价为1）
相同字母的所有格子之间完全连接（互相可达，代价为1）
2. 朴素方法的陷阱
如果直接将所有相同字母的格子之间都建边，复杂度会爆炸：
假设有k个字母'a'的格子，它们之间需要建立O(k²)条边
当k很大时（比如样例3中全是'x'，k=H×W=16），边数达到O((HW)²)，不可接受
3. 关键优化：传送门的一次性使用
核心观察：每个字母的传送机制只需要在第一次遇到该字母时使用一次
为什么？
第一次遇到字母c的格子时，通过一次传送动作，可以到达所有字母c的格子
这些新到达的格子，到起点的距离 = 当前距离 + 1
之后如果再从其他路径到达字母c的格子，距离一定 ≥ 当前距离 + 1
通过BFS的性质，第一次访问时就是最短路径
所以之后再次访问同字母的格子不会得到更短路径
因此，我们可以：
在第一次访问某个字母的任意格子时，将该字母的所有格子都加入队列
然后立即清空这个字母的格子列表
之后遇到相同字母的格子时，不再进行传送操作
算法实现详解
数据结构设计
vector<string> S(H); // 存储迷宫 vector<vector<pair<int, int>>> tele(26); // 26个字母对应的格子列表 vector<vector<int>> dist(H, vector<int>(W, INF)); // 最短距离 queue<pair<int, int>> q; // BFS队列预处理：收集传送门
for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (S[i][j] >= 'a' && S[i][j] <= 'z') { tele[S[i][j] - 'a'].emplace_back(i, j); } } }这里为每个小写字母建立一个列表，存储所有该字母格子的坐标。
BFS主循环
while (!q.empty()) { auto [x, y] = q.front(); q.pop(); int d = dist[x][y]; // 到达终点，直接输出（BFS第一次到达就是最短） if (x == H-1 && y == W-1) { cout << d << "\n"; return 0; } // 1. 行走扩展：向四个方向移动 for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; // 检查边界、不是障碍、且未访问过 if (nx >= 0 && nx < H && ny >= 0 && ny < W && S[nx][ny] != '#' && dist[nx][ny] > d + 1) { dist[nx][ny] = d + 1; q.emplace(nx, ny); } } // 2. 传送扩展：如果当前是字母格子 if (S[x][y] >= 'a' && S[x][y] <= 'z') { int c = S[x][y] - 'a'; // 遍历该字母的所有格子 for (auto [tx, ty] : tele[c]) { // 如果这个格子还没被访问过 if (dist[tx][ty] > d + 1) { dist[tx][ty] = d + 1; q.emplace(tx, ty); } } tele[c].clear(); // 关键：清空，避免重复传送 } }关键点解释
为什么用dist[nx][ny] > d + 1而不是dist[nx][ny] == INF
这是为了处理重复入队的情况。在某些情况下，一个格子可能通过不同路径多次被尝试访问，我们只保留最短距离。
为什么传送后要清空列表
这是算法的核心优化：
第一次遇到字母c时，距离是d
将所有字母c的格子标记为距离d+1
之后如果再遇到字母c的其他格子，距离至少是d+1
而d+1 ≥ d+1，不会产生更短路径
清空后，后续遇到同字母格子时，
tele[c]为空，不会进入循环
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; cin >> H >> W; vector<string> S(H); for (int i = 0; i < H; i++) { cin >> S[i]; } vector<vector<pair<int, int>>> tele(26); for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (S[i][j] >= 'a' && S[i][j] <= 'z') { tele[S[i][j] - 'a'].emplace_back(i, j); } } } const int INF = 1e9; vector<vector<int>> dist(H, vector<int>(W, INF)); queue<pair<int, int>> q; dist[0][0] = 0; q.emplace(0, 0); const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, 1, -1}; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); int d = dist[x][y]; if (x == H-1 && y == W-1) { cout << d << "\n"; return 0; } for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx >= 0 && nx < H && ny >= 0 && ny < W && S[nx][ny] != '#' && dist[nx][ny] > d + 1) { dist[nx][ny] = d + 1; q.emplace(nx, ny); } } if (S[x][y] >= 'a' && S[x][y] <= 'z') { int c = S[x][y] - 'a'; for (auto [tx, ty] : tele[c]) { if (dist[tx][ty] > d + 1) { dist[tx][ty] = d + 1; q.emplace(tx, ty); } } tele[c].clear(); } } cout << "-1\n"; return 0; }