UVa 13116 传送迷宫最短路：分组懒广播与Dijkstra优化

最近刷 UVa 的时候，碰到 13116 Multistory Labyrinth 这题，第一反应以为是个三维迷宫 BFS，结果仔细一读题发现完全不是那么回事。它把“楼层”这个概念抽象成了矩阵里的数字，同数字的房间之间可以互相传送，移动又受楼层差限制，本质上是个带传送门的最短路问题。做这题最有价值的不是 BFS 或者 Dijkstra 本身，而是“同组节点只扩展一次”的优化思路，这个思路在很多迷宫变种题里都能复用。这篇就来完整拆一下题目模型、算法选型和实现细节，适合理清最短路优化逻辑、准备进阶图论题的选手参考。

1. 把迷宫模型拆干净：楼层、移动与传送规则

先别急着写代码，把题目翻译成人话。

1.1 输入怎么读，终点在哪里

输入给的是一个 R 行 C 列的矩阵，每个格子上有一个整数，这个整数代表“楼层号”。起点是左上角 (0,0)，终点是右下角 (R-1,C-1)。楼层号可能出现很大的值，也可能是负数，题目里没有保证值域很小，所以后面存储分组时不能想当然开一个大数组。

你要回答的问题只有一个：从起点走到终点，最少需要多少时间。每次移动消耗 1 单位时间，没有别的代价。

1.2 两种移动的成本与限制

移动方式有两种，这是理解题意的关键。

第一种是普通移动：往上、下、左、右走到相邻格子。但这里有一个限制——如果当前格子的楼层是 a，目标格子的楼层是 b，那么只有 abs(a-b) <= 1 才能走。也就是说，你可以在同一楼层平移，也可以从 3 楼走到 2 楼或 4 楼，但不能从 3 楼一步跨到 5 楼。这个限制非常符合直觉：楼层差距太大，你没法直接走过去，得找电梯或楼梯。

第二种是传送：如果两个格子的楼层号相同，你可以从其中一个直接跳到另一个，哪怕它们相隔十万八千里，也只要 1 单位时间。这相当于每一层楼内部有一套传送系统，把所有同一楼层的房间连成了一个完全图。

把这两种规则合起来看，这个迷宫的本质是：你在地面上按楼层相邻规则走动，遇到同楼层的房间可以瞬间位移。难点在于，同一楼层可能有大量格子，如果每次到达某个格子都把同楼层所有格子扫一遍，复杂度会非常难看。

1.3 一维化：让代码和脑回路都少绕一圈

处理二维网格最短路，我习惯先把坐标压成一维下标：id = r * C + c。这样 BFS 或者 Dijkstra 的队列里存的就是一个整数，不用每次手动维护一个 pair<int,int>，也方便用一维数组存距离。

从一维下标还原坐标也很简单：r = id / C，c = id % C。

这题的分组存储也依赖一维化：读入每个格子时，按楼层号把下标塞进对应的组里。后面做传送扩展时，直接拿到“这个楼层所有格子”的列表。

2. 为什么直接 BFS 会翻车：图论建模的复杂度分析

很多同学一看到“每次移动代价都是 1”，第一反应就是 BFS。但这里有个陷阱。

2.1 传送门让隐式图变得极稠密

如果没有传送门，这就是一个普通的网格最短路，BFS 的复杂度是 O(RC)，非常轻松。

但传送门的存在改变了一切。每层楼有 k 个格子，这 k 个格子之间两两都可以传送，相当于一个 k 个点的完全图，边数是 k(k-1)/2。如果有若干层楼分别有 k1、k2、... 个格子，总边数是 Σ O(ki²)。最坏情况下，矩阵里一大半格子都是同一个楼层号，那 ki ≈ N，边数高达 O(N²)。此时如果显式建边，内存和建图时间直接爆炸。

即使不显式建边，用 BFS 时每访问一个格子，都去遍历整个同楼层组，同样会让复杂度退化成 O(N²)。在一些输入规模较大的题里，比如 R*C 到几万甚至更多时，O(N²) 一定超时。

2.2 朴素 BFS 和朴素建边的双重困境

我把两种笨办法的代价分别说一下。

第一种，显式建完全图。每层楼的 k 个点之间都 push 一条边权为 1 的边，然后跑普通最短路。这个方案在建边阶段就会超时超内存，因为边数不可控。

第二种，不建边，但是 BFS 出队一个格子时，暴力扫描同楼层所有格子。这个方案时间上不可接受：最坏每层楼有 N 个格子，每访问一个格子都要扫一遍同组，总操作量 O(N²)，队列本身还要处理 N 个节点。一旦 N 到 10^5 级别，基本跑不动。

这两种方案其实都忽略了一个关键性质：同一楼层分组之间，并不需要把所有边都实际展开。

2.3 正确的复杂度目标：接近 O(N log N)

我们需要一个方案，让每个格子最多入队常数次，并且每个楼层分组最多被完整遍历一次。这样总复杂度可以做到 O((N + 总分组遍历量) log N)，也就是 O(N log N)，完全能接受。

这个目标看起来很理想，但实现有一个核心难点：如何保证每个楼层分组只遍历一次，同时不丢解。

3. 核心解法：Dijkstra + 分组懒广播

这题最漂亮的地方就在这一步。

3.1 为什么选 Dijkstra 而不是 BFS

虽然边权都是 1，选 BFS 在原理上没错，但 BFS 的层序扩展不容易配合“分组懒广播”的优化逻辑。

Dijkstra 按距离从小到大的顺序弹节点，保证了当某个节点第一次从优先队列里弹出时，它的距离已经是最短距离。这个“第一次弹出即最短路”的性质，正是我们做分组广播的正确性基础。

注意，如果传送成本也是 1，那么整张图边权都是正数，Dijkstra 完全适用。如果某些变种题把传送成本改成 0，那就得退化成 0-1 BFS，不过那是另一个话题。

3.2 每个楼层分组只需要广播一次：关键引理

假设当前弹出节点 u，它所在楼层是 color。我们要不要扫描 color 这一整组的所有格子，尝试把它们的距离更新为 dist[u] + 1？

结论是：color 这一组只需要在第一次弹出该组节点时扫描一次，后面再遇到同组节点，直接跳过传送扩展。

为什么？Dijkstra 的弹出顺序保证，第一个弹出的 color 组节点，它的距离 d 是该组所有节点里的最短距离。用 d + 1 去尝试更新同组所有节点，得到的是该组所有节点通过传送门能拿到的最好上界。如果组里某个节点 x 已经通过普通移动得到更短路径，那么 dist[x] 已经小于 d + 1，不会被覆盖；如果 x 还没更短路径，那 d + 1 就是当前能给到的最优值。

之后当 color 组另一个节点 y 从堆里弹出时，它的距离一定不小于 d。用 dist[y] + 1 去广播，得到的候选值不小于 d + 1，不可能再刷新任何同组节点的距离。换句话说，第二次、第三次广播都是无效劳动。

所以正确做法是：用一个标记数组记录“这个楼层已经被广播过”，第一次弹出时遍历整组，之后不再遍历。

这个优化本质上是把“完全图的所有边”合并成了“一个虚拟源点到所有同组节点的星形边”。完全图的 O(k²) 条边被压缩成 O(k) 条广播边，还不损失正确性。

这里有一个容易踩坑的细节：遍历整组时，不能直接把同组所有节点的距离设置为 d + 1。因为 d + 1 只是一个候选最短路径，同组节点可能早就通过普通移动获得了更短的 dist，也可能稍后通过其他楼层传送获得更短路径。正确做法是，每次发现dist[v] > d + 1才更新，并把更新后的节点重新压入优先队列。

每个格子可以因为普通移动入队多次，也可以因为所在楼层第一次广播时入队一次。一个楼层组只会被完整遍历一次，所以所有组的遍历总量是 O(N)，不会退化。

3.3 可运行的 C++ 主体代码

我用 C++ 写了一个最小可运行版本，直接说重点。

#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; int main() { int T; scanf("%d", &T); while (T--) { int R, C; scanf("%d%d", &R, &C); int N = R * C; vector<int> floor(N); map<int, vector<int>> group; // 楼层 -> 格子下标列表 for (int r = 0; r < R; ++r) { for (int c = 0; c < C; ++c) { int id = r * C + c; scanf("%d", &floor[id]); group[floor[id]].push_back(id); } } vector<int> dist(N, INF); dist[0] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, 0}); map<int, bool> colorDone; // 该楼层是否已经广播过 while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u]) continue; // 过期节点 int r = u / C, c = u % C; // 普通移动：相邻且楼层差 <= 1 for (int k = 0; k < 4; ++k) { int nr = r + dx[k], nc = c + dy[k]; if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue; int v = nr * C + nc; if (abs(floor[v] - floor[u]) > 1) continue; if (dist[v] > d + 1) { dist[v] = d + 1; pq.push({dist[v], v}); } } // 传送广播：同楼层，只处理一次 int color = floor[u]; if (!colorDone[color]) { colorDone[color] = true; for (int v : group[color]) { if (dist[v] > d + 1) { dist[v] = d + 1; pq.push({dist[v], v}); } } } } printf("%d\n", dist[N - 1] == INF ? -1 : dist[N - 1]); } return 0; }

这段代码的核心就一块：if (!colorDone[color])包裹的广播逻辑。其它部分就是标准 Dijkstra。

如果楼层号范围不大，比如保证在 1 到 1000 之间，可以把map<int, vector<int>>换成vector<vector<int>> group(MAXF)，把colorDone换成vector<bool>，能省掉 map 的 log 开销。但如果题面没给值域，用离散化更稳妥。

3.4 另一种建模思路：虚拟楼层节点

除了“分组懒广播”，这题还有一种理解方式：拆出虚拟节点。

对每个楼层 color 建一个虚拟点，把该楼层所有实际格子连到虚拟点，边权 1；从虚拟点连回所有实际格子，边权也为 1。这样原来任意两个同层格子之间的传送，等价于“格子 -> 虚拟点 -> 格子”的两步路径，总代价 2，和直接传送的 1 不一样，所以这个拆法不能直接照搬。

如果传送代价是 0，则可以用“进虚拟点 1、出虚拟点 0”或者反过来。但这题传送代价是 1，虚拟拆点会导致代价偏移。所以在实现上，我推荐直接用懒广播，而不是虚拟拆点。虚拟拆点的思路更适合用来理解“为什么可以把完全图压成星形边”，但不适合直接作为这题的答案。

4. 实现细节与避坑清单

看代码只有几十行，但真写起来有不少细节。

4.1 分组存储用 map 还是离散化

我上面的代码用了map<int, vector<int>>。这样写稳妥，但每个节点入组时要 O(log M) 插入，M 是不同楼层数。如果数据量很大，这个 log 成本累计起来也可观。

更快的做法是：先读一遍整个矩阵，把楼层号收集起来排序去重，做离散化映射，然后再读一遍矩阵（或者存下原始楼层值，读完后统一映射）。这样分组可以用vector<vector<int>> group(K)，其中 K 是不同楼层数量，查找分组下标是 O(1)。

考虑到不少题是多组数据，输入规模可能很大，我建议能离散化就离散化。尤其当楼层号范围超过 10^6 时，千万别开值域数组，否则内存直接爆。虽然我给的示例代码用 map 是为了简洁，但题解里我一般会按离散化实现。

4.2 已处理标记放在哪个时机

“标记已广播”这个动作，必须放在第一次遇到该楼层节点、准备遍历整组之前。如果你先遍历了整组，再设置标记，那没问题；但如果你只设置标记、忘记遍历整组，那这层楼的传送门就完全没用了。

还有一个小坑：有些实现会在读入时就对每个楼层做标记初始化，然后在普通移动里判断“如果目标楼层已经被广播过就不再加入队列”，这是错的。因为普通移动和传送广播是两回事，一个节点即使所在楼层已经广播过，它依然可以被普通移动到达，也必须继续从它身上做普通移动扩展。

换句话说，colorDone只影响“同楼层传送”这个动作，不影响其它移动。

4.3 传送扩展时不能直接把同组点标成最短

我前面强调过，这里再说一次。

假设当前楼层 color 第一次被弹出，距离是 d。正确做法是用 d + 1 去尝试松弛同组所有节点。有些初学者会写成“同组所有节点距离都等于 d + 1”，这会导致结果偏大还是偏小？

如果同组某个节点 x 原本有一条更短的路径，比如通过普通移动走了两步就到了，distance 是 2，而 d + 1 是 5，那直接覆盖会让答案变大。更危险的是，如果你在第一次广播时把同组节点标成“已完成”，那么以后即使有别的路径以更小代价到达它，你也不会再处理它，结果就错了。

所以广播后节点仍然要正常入堆，让 Dijkstra 自己决定最终最短路。

4.4 边界条件：终点就在起点、无解输出

如果 R=1, C=1，起点就是终点，答案应该是 0。上面的代码里，起点在初始化时已经入堆，dist[0] = 0，最后输出 dist[N-1] = 0，没问题。

如果终点不可达，比如网格被不可穿越的楼层差挡住了，且起点终点楼层号不同，也没有任何可传送路径，dist[N-1] 会保持 INF。题目如果没有保证有解，建议输出 -1 或者按题目要求处理。我示例代码里写了-1，但实际提交前要看清输出格式。

另外，起点本身也需要考虑传送：如果起点所在楼层有很多格子，第一次弹出起点时，colorDone[color] 还是 false，会触发一次广播，把所有同层格子都拉进队列。这是对的，不要跳过。

5. 常见错误与排查技法速查

做题过程中我整理过一张排查表，直接给结论。

除了对照表，我还会用微型样例验证逻辑。

拿一个 1 行 4 列的矩阵举例：

3 3 3 3

起点是下标 0，终点是下标 3。第一次弹出 0 时，广播楼层 3，下标 1、2、3 的距离都变成 1。下标 3 直接变 1，所以答案是 1。如果把传送代价理解错，就会得到 3，一测就能发现问题。

再看一个需要普通移动的例子：

1 2 3

1 和 3 楼层差 2，不能直接走。但 2 和 1、3 都差 1，所以路径是 1 -> 2 -> 3，答案 2。这个样例可以验证普通移动的条件有没有写反。

我自己调试时还会顺手打印 dist 数组，检查每个位置的值是否符合手算预期。Dijkstra 的 bug 往往不是算法本身，而是边界判断和标记时机，多打印两步就能定位。

6. 写题解时我踩到的一个很实在的坑

最后分享一个我实现时卡了很久的细节。

一开始我把colorDone[color] = true放在了优先队列弹出节点的“普通移动处理”之后。看起来没什么问题，但后来发现如果把传送广播放在普通移动之前，效率会更好，逻辑也更安全：因为优先队列里可能有多个同楼层节点等待弹出，越早广播，越早给同楼层其它节点一个候选上界，它们入堆后也能更早被弹出。虽然最终复杂度一样，但放在前面能让收敛过程更稳定。

其实更关键的问题是：colorDone的检查应该在普通移动之前还是之后？

从正确性上说，两者都正确。但从 Dijkstra 的性质来想，一个节点弹出时，它的距离已经确定，此时立刻处理该楼层广播，和先做几步普通移动再做广播，广播所用的 d 都是同一个值，结果完全一样。

不过我在第一版代码里犯过一个错误：我在colorDone判断里直接遍历group[color]，但遍历时没有跳过当前节点 u，导致dist[u]被赋成d + 1，然后if (d != dist[u])在下一轮弹出时把 u 判成过期节点，虽然结果有时碰巧对，但逻辑上很脏。所以广播遍历时最好还是加上if (v == u) continue，或者依靠松弛判断挡住，但加一行判断更清晰。

这题做完之后我最大的体会是：遇到“同属性节点两两可达”的图论题，就不要傻傻连完全图，而是想办法把一组节点的所有边压缩成一个广播动作。很多看似复杂的迷宫和传送门问题，最后都能用这个套路把复杂度从 O(N²) 拉回 O(N log N)。这种题刷一题，比刷十题模板 BFS 都有用。