蓝桥杯穿越雷区：带权网格最短路径与Dijkstra算法实战

1. 从"穿越雷区"这个题名说起：它到底在考什么

第一次看到"穿越雷区"这个题名，很多人会下意识觉得这是一道模拟题——画个网格，标上地雷，然后让角色一步步走过去。但真正做过这道题的人都知道，它表面上是个走迷宫的故事，骨子里考的是图论里最基础也最容易被忽视的一类问题：带权网格上的最短路径。

这道题出自第六届蓝桥杯省赛，属于当年C/C++程序设计大学A组的一道压轴级别的题目。它的题干大致是这样的：有一个n×n的方阵，方阵里每个格子要么是空地，要么是雷区。角色从左上角出发，要走到右下角，每走一步只能上下左右移动一格，不能斜着走，也不能走出边界。走到雷区格子会付出额外的代价，问从起点到终点最少需要付出多少代价。

听起来是不是很像我们熟悉的"迷宫最短路"？但它的坑恰恰藏在"代价"这两个字上。普通的BFS求最短路，默认每一步的代价都是1，所以第一次搜到终点就是最优解。可这道题里，进入雷区和进入空地的代价不一样，这就意味着步数最少不等于代价最小。如果你还用朴素的BFS去写，样例可能能过，但隐藏测试点会毫不留情地把你卡掉。

我在带新人刷题的时候，发现一个特别普遍的现象：很多人一看到"网格""最短""从起点到终点"这几个关键词，条件反射就是BFS。这个反射本身没错，但关键在于你得先判断清楚——这张图上的边权是不是都相等。如果边权相等，BFS就是最优解；如果边权不全相等，你就得请出Dijkstra或者0-1 BFS这类工具。这道题就是典型的"边权不全相等"场景，因为进入雷区的代价和进入空地的代价不同。

所以这道题真正的考点，不是"你会不会写BFS"，而是"你能不能在动手之前，先想清楚这道题该用什么算法"。这种先判断模型、再选择工具的思维习惯，才是蓝桥杯这类比赛真正想筛选出来的能力。后面我会把这道题从建模、算法选型、代码实现到调试踩坑，一层层拆开讲透，让你不仅能把这道题做对，还能把这类题的通用套路装进脑子里。

2. 把故事翻译成图论模型：网格、节点与边权

2.1 网格问题的标准建模方式

任何一道网格路径题，第一步都是把它翻译成图论语言。这一步看起来简单，但翻译得准不准，直接决定了后面算法选得对不对。

具体到"穿越雷区"这道题，建模方式是这样的：把每一个格子看作图中的一个节点，节点用坐标(i, j)来标识，其中i表示行，j表示列。如果两个格子上下左右相邻，就在它们对应的节点之间连一条无向边。因为角色可以往四个方向走，所以每个内部节点最多有四条边，边界上的节点边数更少。

边的权重怎么定？这就是这道题的核心。从当前格子走到相邻格子，需要付出的代价取决于目标格子的性质。如果目标格子是空地，代价是某个较小的值（比如1）；如果目标格子是雷区，代价是某个较大的值（比如2或者题目给定的其他数值）。注意这里有个容易搞混的点：代价是算在"进入"这个格子上，还是算在"离开"这个格子上？不同的题目表述不一样，一定要看清楚。

提示：很多人在这一步栽跟头，是因为没搞清楚起点格子的代价算不算。通常题目会明确说"起点不需要付出代价"或者"起点本身也有代价"，读题时务必逐字确认。

2.2 为什么不能简单地把雷区当成障碍物

我见过不少人的第一反应是：雷区嘛，绕开不就行了，把它当成墙不就好了？这个思路在"雷区不可通行"的题目里是对的，但在这道题里是错的。因为题目说的是"穿越雷区"，意味着雷区是可以走的，只是走进去要付出更高的代价。

这个区别非常关键。如果雷区是墙，那问题就退化成普通的迷宫可达性问题，BFS或者DFS都能解决。但雷区可通行且代价更高，问题就变成了带权最短路。你可以把雷区想象成高速公路上的收费站——你可以走这条路，但要多交钱；你也可以绕路走免费的普通公路，但可能绕远。到底哪个更划算，得算过才知道。

这就引出了一个很反直觉的结论：有时候穿过一片雷区反而比绕一大圈空地更省代价。很多人在做题时会本能地避开雷区，结果算出来的答案偏大。正确的做法是让算法自己去权衡，而不是人为地预设"雷区不能走"。

2.3 边权设计的几种常见变体

蓝桥杯这类题在边权设计上经常玩花样，我总结了几种常见的变体，你在做题时可以对号入座：

"穿越雷区"属于第二种双代价模型。如果题目里空地和雷区的代价恰好是0和1，那就可以用0-1 BFS把复杂度压到O(n²)；如果代价是任意正整数，那就老老实实上Dijkstra。这一点在后面算法选型那一节我会展开讲。

3. 算法选型：BFS、0-1 BFS还是Dijkstra

3.1 先判断边权是否统一，这是分水岭

选算法的第一步永远是看边权。我把它总结成一句话：边权全相等用BFS，边权只有0和1用0-1 BFS，边权是任意非负数用Dijkstra。这三者的关系是层层递进的，后者能解决前者的问题，但前者在特定条件下更快。

对于"穿越雷区"，你需要先确认题目给的代价具体是什么。如果题目说空地代价是0、雷区代价是1，那这就是标准的0-1 BFS场景。如果题目说空地代价是1、雷区代价是2，那严格来说得用Dijkstra，但因为只有两种权值，也可以用一种"双端队列+优先队列"的混合写法来优化。

我在实际做题时有个习惯：先看数据范围。如果n只有几十，那用什么算法都无所谓，Dijkstra写起来最稳；如果n到了几百甚至上千，那就得抠复杂度了，0-1 BFS的O(n²)会比Dijkstra的O(n²logn²)快不少。

3.2 普通BFS为什么在这道题上会翻车

普通BFS的本质是"按层扩展"，它假设先被访问到的节点距离一定更短。这个假设成立的前提是每条边的权重都相同。一旦边权不同，先被访问到的节点就不一定是最优的了。

举个具体的例子。假设从起点出发，有两条路到终点：第一条路走3步，每步都踩雷，总代价是3×2=6；第二条路走5步，全是空地，总代价是5×1=5。普通BFS会先搜到第一条路（因为步数少），然后兴高采烈地返回6，但正确答案是5。这就是典型的"步数最少不等于代价最小"。

要修复这个问题，有两种思路：一是把BFS换成能处理带权图的Dijkstra；二是对BFS做改造，让它支持"同一个节点可以被多次更新"。后者其实就是SPFA的思路，但在网格图上容易退化，不如直接上Dijkstra稳。

3.3 0-1 BFS的巧妙之处

如果这道题的代价恰好是0和1，那0-1 BFS是最优雅的解法。它的核心思想是：用双端队列代替普通队列，遇到边权为0的边就把新节点压到队首，遇到边权为1的边就压到队尾。这样就能保证队列里的节点距离是单调不减的，从而维持BFS的正确性。

这个技巧我第一次见的时候觉得特别巧妙。它的本质是"用双端队列模拟优先队列"，因为只有两种权值，所以不需要真正的堆，一个deque就够了。复杂度是O(V+E)，在网格图上是O(n²)，比Dijkstra快一个log。

不过要注意，0-1 BFS只适用于边权为0和1的情况。如果题目给的代价是1和2，你就不能直接套用，得先把权值归一化，或者干脆用Dijkstra。我见过有人硬套0-1 BFS结果WA了一整页，就是因为没注意这个前提。

3.4 Dijkstra在网格图上的实现要点

Dijkstra是带权最短路的通用解法，网格图上用起来也很直接。核心步骤是：维护一个距离数组dist，初始时起点的dist为0，其余为无穷大；用一个优先队列（小根堆）存(距离, 节点)的二元组；每次取出距离最小的节点，如果它已经被处理过就跳过，否则用它去松弛它的四个邻居。

在网格图上实现Dijkstra有几个细节值得注意。第一，节点编号可以用i×n+j的方式压缩成一维，这样距离数组和优先队列都更好写。第二，方向数组用dx和dy两个数组来表示上下左右，比写四遍if要清爽得多。第三，边界判断要放在松弛之前，避免数组越界。

#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int n; int cost[105][105]; // 每个格子的进入代价 int dist[105][105]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int dijkstra() { memset(dist, 0x3f, sizeof(dist)); priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq; dist[0][0] = 0; pq.push({0, 0, 0}); while (!pq.empty()) { auto [d, x, y] = pq.top(); pq.pop(); if (d > dist[x][y]) continue; if (x == n-1 && y == n-1) return d; for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; int nd = d + cost[nx][ny]; if (nd < dist[nx][ny]) { dist[nx][ny] = nd; pq.push({nd, nx, ny}); } } } return dist[n-1][n-1]; }

这段代码里有个小优化：当弹出的节点已经是终点时，可以直接返回，不用等队列清空。因为Dijkstra的性质保证了第一次弹出终点时，它的距离就是最终答案。

4. 代码实现中的那些坑：从读题到AC的完整链路

4.1 输入格式的坑：字符还是数字

蓝桥杯的题目在输入格式上经常埋雷。"穿越雷区"这类题，输入可能是一个n×n的字符矩阵，用'A'表示空地、'B'表示雷区，也可能是数字矩阵，用0和1表示。这两种输入的处理方式完全不同。

如果是字符矩阵，读入时要注意换行符和空格。用cin >> ch逐个读字符是最稳的，因为它会自动跳过空白字符。如果用getline，就得小心每行末尾的换行符会不会被读进来。我见过太多人因为输入处理不当，导致矩阵整体错位，然后对着样例debug半天。

如果是数字矩阵，用scanf("%d")或者cin >> num都可以，但要注意数字之间可能有空格也可能没有。稳妥的做法是逐个字符读，遇到数字就转换。

注意：读题时一定要确认矩阵的行列是从0开始还是从1开始。虽然逻辑上不影响，但写代码时如果搞混了，边界判断就会出错。

4.2 起点和终点的代价到底算不算

这是这道题最容易出错的地方，没有之一。题目通常会说"从起点出发，走到终点"，但起点的代价算不算、终点的代价算不算，不同的表述会导致答案差一个常数。

我的处理习惯是：先把起点的dist设为0，然后在松弛邻居时加上邻居的代价。这样起点的代价天然不算，终点的代价会在最后一次松弛时被加上。如果题目明确说终点代价不算，那就在返回答案时减去终点的代价。

这个细节看起来小，但在比赛中就是AC和WA的区别。我建议你在草稿纸上画一个2×2的小例子，手动算一遍，确认自己的代价计算方式和题目一致，再开始写代码。

4.3 优先队列的比较器写法

C++的priority_queue默认是大根堆，要用小根堆得自己写比较器。对于pair或者tuple，可以用greater<>，但要注意头文件要包含 。如果用的是自定义结构体，就得重载operator<或者写一个仿函数。

struct Node { int d, x, y; bool operator<(const Node& other) const { return d > other.d; // 注意这里是大于号，因为priority_queue默认大根堆 } };

这个"大于号"是很多人第一次写会搞反的地方。记住一个口诀：priority_queue的operator<返回true表示优先级低，所以要让距离小的优先级高，就得写d > other.d。

4.4 距离数组的初始化与溢出防范

距离数组初始化成INF时，INF的取值要小心。如果用0x3f3f3f3f，两个INF相加不会溢出int；如果用INT_MAX，相加就会溢出成负数，导致松弛逻辑出错。这是竞赛代码里的经典陷阱，我强烈建议统一用0x3f3f3f3f。

另外，memset按字节赋值，只能用来初始化0、-1或者0x3f这类特殊值。如果你想初始化成其他数，得用fill或者循环。这一点在初始化dist数组时经常被忽略。

5. 调试与验证：怎么确认自己的答案是对的

5.1 用手算小样例验证代价逻辑

写完代码后，别急着提交，先自己造几个小样例手算一遍。比如一个2×2的矩阵，起点在左上，终点在右下，中间两个格子一个是空地一个是雷区。手动列出所有可能的路径，算出每条路径的代价，取最小值，然后和程序输出对比。

这个过程能帮你快速定位是代价计算错了，还是算法选错了。如果手算结果和程序输出不一致，先检查代价的加减逻辑，再检查算法是否正确处理了带权情况。

5.2 对拍：用暴力DFS验证Dijkstra

对于n比较小的情况（比如n≤8），可以写一个暴力DFS枚举所有路径，求出最小代价，然后和Dijkstra的结果对拍。这个方法虽然土，但极其有效。我当年做这道题的时候，就是靠对拍发现了自己在边界处理上的一个bug。

对拍的代码很简单：DFS从起点出发，标记访问过的节点，递归四个方向，到达终点时更新最小值，回溯时取消标记。注意网格图上DFS要防止走回头路，所以需要visited数组。

int best = INF; bool vis[10][10]; void dfs(int x, int y, int cur) { if (cur >= best) return; // 剪枝 if (x == n-1 && y == n-1) { best = min(best, cur); return; } for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (vis[nx][ny]) continue; vis[nx][ny] = true; dfs(nx, ny, cur + cost[nx][ny]); vis[nx][ny] = false; } }

5.3 边界条件的专项测试

网格题的边界条件是最容易出bug的地方。我建议专门造几组边界样例：n=1的情况（起点就是终点）、起点或终点本身是雷区的情况、矩阵全是雷区的情况、矩阵全是空地的情况。这几组样例能覆盖大部分边界bug。

特别是n=1的情况，很多人写的代码会直接返回INF或者崩溃，因为循环根本没进去。正确的处理是在函数开头判断如果n==1，直接返回起点的代价（或者0，取决于题目）。

6. 从这道题延伸出去：网格最短路题的通用套路

6.1 状态扩展：当最短路遇上额外约束

"穿越雷区"是一道纯粹的带权最短路题，但蓝桥杯里还有很多网格题会在最短路的基础上加额外约束。比如"最多只能踩k个雷"，这时候就需要把状态从(i, j)扩展成(i, j, k)，用三维的dist数组来记录。这种技巧叫状态扩展或者分层图，是网格题进阶的必经之路。

状态扩展的核心思想是：把额外的约束编码进节点里，让原本不合法的路径变成合法的。比如"最多踩k个雷"，就把踩雷次数作为第三维，每次进入雷区时第三维加1，超过k的转移直接跳过。这样问题就转化成了在扩展后的图上求最短路，算法框架完全不变。

6.2 双向搜索：当n很大时的优化手段

如果n到了几千，单向的Dijkstra可能会超时。这时候可以考虑双向Dijkstra：从起点和终点同时开始搜索，当两个搜索 frontier 相遇时，把两边的距离加起来就是答案。理论上能把搜索空间从O(n²)降到O(n²/2)，实际效果取决于图的结构。

不过双向Dijkstra的实现比单向复杂不少，需要维护两个距离数组和两个优先队列，还要处理"相遇"的判断逻辑。在蓝桥杯这种时间紧张的比赛里，除非n确实很大，否则我不建议轻易上双向，容易写错。

6.3 网格题的常见变体清单

我把网格最短路相关的常见变体整理成一张表，方便你以后遇到类似题目时快速定位：

这张表里的每一行，都值得你单独找几道题练手。网格最短路是算法竞赛里的高频考点，把这几种变体吃透，遇到新题时就能快速识别出它属于哪一类。

7. 我在刷这道题时踩过的几个真实坑

第一次做"穿越雷区"的时候，我信心满满地写了个BFS，样例过了，提交WA。当时我还以为是输入格式的问题，改了半天输入，还是WA。后来静下心来重新读题，才发现自己漏看了"代价"两个字，把带权问题当成了无权问题。

第二次改成了Dijkstra，结果又WA了。这次的问题出在起点的代价上。我习惯性地在松弛时加上了起点的代价，但题目里起点是不需要付代价的。改了这一行之后，终于AC了。

第三次是帮别人看代码时发现的另一个坑：有人用0-1 BFS做，但题目给的代价是1和2，不是0和1。他直接把2当成1处理了，结果答案偏小。这个坑的教训是：用任何算法之前，先确认它的前提条件是否满足。

这几个坑看起来都很低级，但每一个都真实地发生过。我的体会是，做算法题最怕的不是不会，而是"以为自己会"。读题要慢，选算法要稳，写代码要细，验证要狠。这十六个字是我刷了这么多年题总结出来的，送给你。

最后再分享一个实用的小习惯：每次写完一道网格最短路题，我都会把代码里的方向数组、边界判断、代价计算这三处单独拎出来检查一遍。这三处是bug的高发区，检查一遍花不了两分钟，但能省下大量debug时间。