迷宫传送[最短路径]

问题描述​有一个由 H 行、W 列的网格组成的迷宫。用 (i, j) 表示从上往下第 i 行、从左往右第 j 列的格子。每个格子 (i, j) 的类型由一个字符 S(i, j) 给出其含义如下. 空单元格# 障碍单元格小写英文字母 (a–z) 传送单元格在迷宫中你可以按任意顺序执行以下两种动作次数不限行走从当前单元格移动到相邻的上、下、左、右单元格之一。但不能移动到障碍格或网格外。传送当你位于传送单元格时可以移动到相同字母的任意传送单元格。请判断能否从单元格 (1,1) 移动到单元格 (H,W) 。如果可能请输出所需的最小总动作次数否则输出 -1。约束条件​1 ≤ H, W ≤ 1000H × W ≥ 2H, 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相同字母的所有格子之间完全连接互相可达代价为12. 朴素方法的陷阱如果直接将所有相同字母的格子之间都建边复杂度会爆炸假设有k个字母a的格子它们之间需要建立O(k²)条边当k很大时比如样例3中全是xkH×W16边数达到O((HW)²)不可接受3. 关键优化传送门的一次性使用核心观察每个字母的传送机制只需要在第一次遇到该字母时使用一次为什么第一次遇到字母c的格子时通过一次传送动作可以到达所有字母c的格子这些新到达的格子到起点的距离 当前距离 1之后如果再从其他路径到达字母c的格子距离一定 ≥ 当前距离 1通过BFS的性质第一次访问时就是最短路径所以之后再次访问同字母的格子不会得到更短路径因此我们可以在第一次访问某个字母的任意格子时将该字母的所有格子都加入队列然后立即清空这个字母的格子列表之后遇到相同字母的格子时不再进行传送操作算法实现详解数据结构设计vectorstring S(H); // 存储迷宫 vectorvectorpairint, int tele(26); // 26个字母对应的格子列表 vectorvectorint dist(H, vectorint(W, INF)); // 最短距离 queuepairint, 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的格子标记为距离d1之后如果再遇到字母c的其他格子距离至少是d1而d1 ≥ d1不会产生更短路径清空后后续遇到同字母格子时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; vectorstring S(H); for (int i 0; i H; i) { cin S[i]; } vectorvectorpairint, 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; vectorvectorint dist(H, vectorint(W, INF)); queuepairint, 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; }