1. 先把故事外壳剥掉这道题的内核是无权网格图上的最短路“BFS 写旅游题”这个说法听着有点绕但凡是刷过网格地图类搜索题的人看到标题里那三个字母心里基本就有数了——这活儿的本质就是在无权图上求最短路径。这道来自某题库 1996 号的题目题干被包装成小 W 出门旅游、在景区地图上找路线可一旦把“景区”“游客”“景点”这些词换成“节点”“源点”“目标点”剩下的骨架和模板题没有任何区别。我先把话说明白原题面我这里拿不到完整版本下面按这类“旅游”命名题最常见的形态来展开——一个 n 行 m 列的字符网格#表示走不过去的山体或水域.表示可通行的平地S是入口T是出口每次只能上下左右走一格每格耗时 1问从入口到出口最少要走几步走不到输出 -1。这是绝大多数同名题的标准设定如果你手上的题面在细节上有出入比如加了步数上限、加了多个景点、加了补给点第 4 章专门讲这些变种怎么接思路是通用的。这篇文章适合谁看如果你刚学完 BFS 的理论、只会背模板但一遇到具体题目就不知道怎么下手那这篇正好如果你已经能独立写出 BFS但总在细节上翻车——数组越界、读入读到换行、多组数据不清空、队列开到爆内存——那第 3 章和第 5 章值得你重点看那些坑我一个个踩过。核心关键词先摆出来BFS、广度优先搜索、最短路径、网格图、队列、访问标记、多源扩展、0-1 BFS。整篇文章围绕这几个点转不跑偏。2. 为什么这题非 BFS 不可三类搜索的适用边界2.1 从“每步代价相同”推出 BFS 的合法性选算法之前先问一个问题这张图上每条边的“代价”是不是一样这道题里答案很明确——不管你是从 (1,1) 走到 (1,2)还是从 (100,100) 走到 (100,101)都只花一步代价恒等于 1。这个前提太重要了它直接决定了 BFS 能用。BFS 的正确性来自一个不变量队列里节点的距离值单调不减。因为每扩展一层距离就加 1所以队列天然是按距离从小到大排好的。这就意味着任何节点第一次被访问到时它拿到的距离一定就是最短距离后面不可能再出现更短的走法。我常跟人打这个比方往平静的水面扔一颗石子涟漪一圈一圈往外扩第一圈到达的岸边肯定是最先被波及的不存在“第二圈比第一圈先到”的情况。BFS 就是这个涟漪。理解了这一点后面很多写法上的取舍就顺理成章了比如“为什么入队的时候就要打标记”这个问题本质就是在维护这个不变量。2.2 DFS 为什么不行Dijkstra 为什么是杀鸡用牛刀有人可能会想DFS 也能遍历全图啊为什么不用它因为 DFS 是“一条道走到黑”它找到的第一条路径完全可能是绕了远路的那种。要想用 DFS 求最短路你得把所有路径都枚举一遍再取最小值复杂度直接爆炸指数级起步稍微大点的图就跑不动了。DFS 适合的是“是否存在一条路径”“连通块计数”“拓扑排序”这类问题求最短路不是它的主场。那 Dijkstra 呢Dijkstra 当然能解而且结果一定对。但它是为带权图设计的需要堆来维护当前最小距离复杂度是 O(E log V)。这道题所有边权都是 1用 Dijkstra 相当于拿高射炮打蚊子——结果没错但白白多背一个 log代码还长一截。什么时候必须请出 Dijkstra当题目里出现了不同的移动代价比如平地上走一步花 1、爬山花 3、坐缆车花 0这时候 BFS 的“等层扩展”就不成立了Dijkstra 或者 0-1 BFS 才管用。这个判断标准我建议记牢边权全为 1 用 BFS边权只有 0 和 1 用双端队列 0-1 BFS边权任意非负用 Dijkstra。2.3 数据规模反推为什么 O(nm) 是道生死线竞赛题给出的数据范围往往就是在暗示算法。这类网格题常见的是 n, m ≤ 1000也就是说总格子数最多一百万。BFS 的复杂度是 O(nm)因为每个格子最多入队一次、出队一次每次出队检查四个方向总操作数大约是 4nm一百万的四倍就是四百万次基本操作跑进 1 秒绰绰有余。反过来看如果这题允许四个方向走且边权不等那最坏得用 Dijkstra复杂度变成 O(nm log(nm))一百万乘以 20两千万次操作虽然还能过但常数已经吃紧了。再往上如果 n, m 到 2000四百万个格子Dijkstra 基本就没戏了。你在读题的时候如果看到数据范围在 10^6 这个量级脑子里第一反应就该是“线性或近线性算法”BFS 正好卡在这个位置上。注意判断能不能用 BFS先看边权是否统一再看数据规模是否允许 O(nm)。这两个条件缺一不可很多人只看了第一个就动手结果数据范围一大代码里常数没优化好卡在最后几个点。3. 核心设计状态、距离数组和队列怎么配3.1 状态表示一个格子就是一个状态什么时候才需要加维度状态定义是整个搜索的地基。这道题的状态非常朴素——坐标 (x, y) 就是状态不需要额外维度。因为在这个模型里你站在哪个格子上能做的事完全一样与你怎么走到这里的、走了多少步都无关。这种“无后效性”是 BFS 能用一个二维数组存距离的前提。但有些题就必须加维度了。举个例子如果景区里散布着若干把钥匙你必须先拿到钥匙才能通过某道门那状态就得从 (x, y) 升级成 (x, y, 已收集的钥匙集合)用二进制状态压缩存钥匙。再比如题目限制“每个格子只能经过一次”那状态还得再带上访问历史规模直接爆炸这时候往往就得换思路了。我总结的判断方法是问自己“两个不同的到达方式会不会影响接下来的决策”。如果不会二维就够如果会就得把那个“影响决策的因素”塞进状态里。这道题显然不会所以老老实实用二维数组。3.2 距离数组和标记数组能不能合成一个新手常见的写法是开两个数组一个visited存能不能到一个dis存步数。能跑但没必要。更省事的做法是把两者合一用一个dis数组初始值全设成 -1-1 表示没访问过非负表示最短距离。这样判断“是否访问过”就变成判断dis[nx][ny] -1一行搞定还省了一半内存。这里有个细节值得掰开说。memset(dis, -1, sizeof(dis))之所以能把 int 数组全部置为 -1是因为 -1 的补码是 0xFFFFFFFF每个字节都是 0xFFmemset 按字节填充正好填出这个值。如果你想把数组置成 1就没这么好运气了memset 按字节填只能得到 0x01010101也就是 16843009不是 1。这个坑必须记住memset 只适合置 0、-1 和 0x3f 这类所有字节相同的值。想初始化成其他数老老实实写循环。另一种常见写法是用0x3f3f3f3f表示无穷大好处是两两相加不会溢出 int方便做松弛操作。但这题用不上松弛-1 更直观我倾向于用 -1。3.3 队列STL 容器还是手写数组该怎么选队列这块有两套写法各有各的道理。用 STL 的queuepairint,int写起来最省心不用管容量不用管头尾指针push 和 pop 语义清晰。缺点是有额外的封装开销每次 push 都要在底层容器上做一次操作节点数上百万的时候累积起来的常数损耗不算小。我做过粗略对比同样的逻辑手写数组队列在百万级节点规模下通常能快上一截具体差多少跟编译器、标准库实现都有关系但方向是确定的。手写队列的关键是容量要开对。上界很好推每个格子最多入队一次所以队列长度不可能超过 n × m。给数组开n * m的大小就绝对安全不需要多开因为同一时刻队列里的元素绝不会超过总状态数。但如果你的状态加了维度比如变成 (x, y, 状态)那上界就要乘以状态的种类数这个一定要算清楚。// 手写队列容量严格按最大可能状态数开 const int MAXN 1005; int qx[MAXN * MAXN], qy[MAXN * MAXN]; int head 0, tail 0; // 区间为 [head, tail) qx[tail] sx; qy[tail] sy; tail; // 出队取 qx[head], qy[head]然后 head // 入队qx[tail] x; qy[tail] y; tail用左闭右开的[head, tail)区间判断队空就是head tail比用head tail少很多心智负担。这个习惯我从一开始就养成了后来写所有需要手写队列的题都没再因为这个出过错。提示队列容量按“最大状态数 × 每状态入队次数”计算。如果实现正确入队即标记每状态只会入队一次如果没有及时标记同一状态可能反复入队这时候固定容量的数组就会溢出表现为莫名其妙的运行时错误或者答案错乱。4. 动手实现从读入到输出一步步写扎实4.1 读入环节字符网格最容易翻车的地方我能负责任地说网格题里一半以上的“莫名其妙 WA”都出在读入上。坑在哪第一个坑是换行符。如果你用scanf(%c, c)或者cin c一个一个字符读行末的\n有些环境下还有\r会被当成一个有效字符读进来于是你的网格整体错位一格边界判断全乱。这个 bug 极其隐蔽因为程序不会崩只是答案不对而且小数据有时候还能碰巧对。第二个坑是行末残留。如果某一行读了 n 个字符但实际这行有 n1 个字符多一个换行下一行读的时候就会先读到换行。这种情况用getchar()手动吞掉换行可以解决但代码里很容易漏掉某处。我的标准做法是字符串整行读下标从 1 开始。for (int i 1; i n; i) { scanf(%s, g[i] 1); // 从第 1 列开始存g[i][0] 空着 }%s会自动跳过前导空白包括换行读到下一个空白为止所以完全不用担心换行污染。g[i] 1这个写法让字符串从下标 1 开始写第 0 列空出来好处是边界判断可以直接写x 1 || x n不用处理 -1 下标省心很多。下标从 0 开始当然也行但那样边界判断就得写x 0 || x n而且dis[x-1][y]这种写法在 x0 时就是负下标容易出错。从 1 开始是我在网格题上最推荐的习惯多浪费一行一列的内存换来的是少一堆越界 bug。4.2 方向数组和边界判断顺序不能反方向数组是网格题标配const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; // 上、下、左、右写的时候注意 dx 和 dy 要配对上对应 (-1, 0)下对应 (1, 0)左对应 (0, -1)右对应 (0, 1)。我见过有人写成dx {0, 0, -1, 1}、dy {-1, 1, 0, 0}逻辑上其实也对只是方向顺序变了但如果配错对——比如把 (-1, 0) 和 (0, -1) 搞混——就会出现“走斜线”的诡异现象答案偏差很大。更关键的是边界判断必须在访问数组之前int nx x dx[d], ny y dy[d]; if (nx 1 || nx n || ny 1 || ny m) continue; // 先判越界 if (g[nx][ny] #) continue; // 再判障碍 if (dis[nx][ny] ! -1) continue; // 最后判是否访问过 dis[nx][ny] dis[x][y] 1; qx[tail] nx; qy[tail] ny; tail; // 入队这个顺序反了就是未定义行为。如果你先写if (dis[nx][ny] ! -1)而 nx 是 -1 或者 n1那就是在访问数组外面的内存读到的可能是任意值。轻则答案错重则在某些环境下直接崩溃。这个顺序我是当成肌肉记忆来练的写完先扫一眼这三行的顺序对不对。4.3 完整代码与逐段拆解下面这版是基础版的完整实现求 S 到 T 的最少步数走不到输出 -1#include cstdio #include cstring const int MAXN 1005; int n, m, sx, sy, tx, ty; char g[MAXN][MAXN]; int dis[MAXN][MAXN]; int qx[MAXN * MAXN], qy[MAXN * MAXN]; const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; int bfs() { memset(dis, -1, sizeof(dis)); // -1 表示未访问 int head 0, tail 0; dis[sx][sy] 0; qx[tail] sx; qy[tail] sy; tail; while (head tail) { int x qx[head], y qy[head]; head; if (x tx y ty) return dis[x][y]; // 提前返回 for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 1 || nx n || ny 1 || ny m) continue; if (g[nx][ny] #) continue; if (dis[nx][ny] ! -1) continue; dis[nx][ny] dis[x][y] 1; qx[tail] nx; qy[tail] ny; tail; } } return -1; // 队列空了还没碰到终点说明不连通 } int main() { scanf(%d %d, n, m); for (int i 1; i n; i) { scanf(%s, g[i] 1); } for (int i 1; i n; i) for (int j 1; j m; j) { if (g[i][j] S) { sx i; sy j; } if (g[i][j] T) { tx i; ty j; } } printf(%d\n, bfs()); return 0; }几个值得单独拎出来说的点。第一起点入队时立刻置 dis 为 0。这一步如果忘了起点会被当成未访问它自己可能被邻居重新入队一次虽然结果大概率还是对的因为撞到dis ! -1就跳过了但如果起点周围有环可能出现距离值被覆盖的情况。更重要的是忘了这一步说明你没想清楚“dis 数组承担了双重职责”这件事。第二提前返回放在出队时而不是入队时。理论上入队时判断也能提前返回而且能省一点队列操作但要注意入队时的 dis 值也是正确的因为入队时就赋好了值。两种写法都对我习惯放在出队因为此时这个节点的距离一定已经是最小的语义上更严谨也避免“终点就是起点”这种边界情况的特殊处理。第三主函数里那次全图扫描别忘了。如果某个格子既是 S 又是 T题目数据可能这么恶心或者根本没找到 S那 sx、sy 就是全局变量默认的 0起点跑到 (0,0) 去了全盘皆错。稳妥的做法是初始化时把 sx 设成一个不可能的值找到后再用找不到就特判。4.4 内存和常数把限制算明白再写很多题目的内存限制是 64MB 或者 128MB网格题特别容易爆。我们来算笔账。假设 n m 1000格子总数 10^6。char g[1005][1005]约 1MBint dis[1005][1005]约 4MBqx[1000*1000] qy[1000*1000]都是 int约 8MB加起来 13MB没问题。但如果你的 dis 用int队列又用queuepairint,int每对 8 字节还要加上 deque 的块状分配开销内存会往上飘实际占用通常比理论值多出不少。如果 n, m 涨到 2000格子数变成 4×10^6dis就是 16MB两个 int 队列就是 32MB合计超过 50MB这时候就危险了。解决办法有两个一是把 dis 换成short距离最大不超过 4×10^6short 装不下但如果数据保证答案不大就够用需要谨慎评估二是把二维坐标压成一维编码id x * m y队列只存 int容量减半。第二种更通用我一般不嫌麻烦就直接用一维编码反正解码也就两行。常数方面还有个小技巧把dis[x][y]先取出来存到局部变量int d0 dis[x][y];循环里用d0 1。因为dis[x][y]在四方向循环里被反复读取编译器不一定能把它提到循环外涉及内存别名分析手动提出来能少几次访存。这个优化在百万级数据上能看出一点差别但别指望有数量级的提升。5. 题目变形三种常见追问怎么接5.1 加一个步数上限提前终止和剪枝的位置最常见的变形是小 W 只有 K 点体力每走一步消耗 1 点问他最多能游览多少个不同的格子或者能不能到达终点。这本质上就是限制最大扩展层数。最简单的改法是在出队时判断while (head tail) { int x qx[head], y qy[head]; head; if (dis[x][y] K) continue; // 已经走满 K 步不再往外扩 for (int d 0; d 4; d) { // ... 正常扩展 } }这个剪枝为什么对因为 BFS 是按层扩展的队列里的 dis 单调不减一旦某个节点的 dis 达到 K它后面所有节点的 dis 都 ≥ K都不可能再往外扩展了。所以直接continue掉省下四方向的检查。注意这里写 K而不是 K。因为正常情况下 dis 不会超过 K超了就不会被入队写也没错但更能表达意图。我更推荐在扩展时做限制也就是判断if (dis[x][y] 1 K) continue;这样从源头上就不会有超限节点入队队列更干净。如果要统计“K 步内能到达的格子数”在 BFS 结束后扫一遍 dis 数组统计有多少个位置的值在[0, K]区间内就行。这一步别忘了把起点算进去dis 为 0 的那个我见过有人统计时漏掉起点差 1 分。还有个容易忽略的点如果 K 已经大于等于网格的直径那整个连通块都能走到此时 BFS 会遍历完所有可达格子复杂度还是 O(nm)不会因为 K 大而变慢。这个性质让剪枝显得很安全。5.2 加多个起点多源 BFS 的初始化只需改一行另一种变形是景区有多个入口小 W 可以从任意一个入口进问到达某个景点的最短距离。这就是多源最短路。关键洞察是多源 BFS 等价于“加一个超级源点超级源点到所有起点的距离都是 0”。所以实现上你只需要把所有起点在初始化时全部入队dis 全部设为 0剩下的一行都不用改。memset(dis, -1, sizeof(dis)); int head 0, tail 0; for (int i 0; i (int)starts.size(); i) { int x starts[i].first, y starts[i].second; dis[x][y] 0; qx[tail] x; qy[tail] y; tail; } // 后面完全一样为什么这样是对的直觉上把多个石子同时扔进水里涟漪从多个中心同时往外扩某个位置最先被哪圈涟漪扫到它的距离就是到最近源点的距离。严格证明还是靠那个不变量队列里的距离单调不减任何节点第一次被访问时拿到的就是最小值。这里有个坑如果多个起点有重复或者某个起点是障碍直接入队会导致错误。入队前必须做一次合法性检查把不合法的起点过滤掉。我就吃过这个亏题目数据里给了一个障碍点作为起点结果程序直接从这个障碍点往外扩展答案偏小。还有一个进阶版本如果起点本身有“代价”比如从不同的门进要买不同价格的票那就不能用简单多源 BFS 了得改成带初始距离的优先队列本质退化成 Dijkstra。5.3 加补给点和传送门BFS 什么时候就不够用了这是最能体现思维深度的一类变形。假设景区里散布着补给站走到补给站体力回满。这时候还能用 BFS 吗如果每个补给站只用一次即回满后不会重复触发其实还能做。因为 BFS 保证第一次到达补给站时距离最短而“越早到达补给站越好”是成立的——你到得越早剩余体力越多后续能走的范围越大。所以可以在 BFS 里加一个状态维度表示“当前体力”或者用分段 BFS 的方式处理。但如果补给可以反复触发或者传送门能双向跳问题立刻复杂起来。传送门的边权是 0跳过去不花时间或者 1普通移动边权是 1这时候图里出现了 0 权和 1 权混合的情况普通 BFS 就失效了。正确的工具是双端队列 BFS0-1 BFS遇到边权为 0 的转移把新节点 push 到队首边权为 1 的转移push 到队尾。这样队列里依然能保持距离单调复杂度还是 O(V E)。// 0-1 BFS 的核心按边权决定插队首还是队尾 if (w 0) dq.push_front(nv); else dq.push_back(nv);再复杂一点如果传送门有使用次数限制、或者移动代价是任意正整数比如爬坡花 3 点体力、平路花 1 点那就只能上 Dijkstra 加优先队列了。判断标准还是那句老话看边权。边权全是 1 用 BFS0/1 混合用双端队列任意非负用堆。我在实际做题时养成了一个习惯读完题先在纸上写下“状态是什么、转移是什么、每条转移的代价是多少”这三行写清楚了用哪个算法是水到渠成的事根本不用纠结。6. 常见问题与排查实录6.1 五种看起来没毛病的 WA第一种入队时不标记出队时才标记。这是最经典的性能陷阱。如果你在出队时才把 visited 置真那么同一个节点在被访问之前可能被它的多个邻居分别入队一次队列里堆满重复元素。在网格图上一个格子最多有 4 个邻居最坏情况队列长度会膨胀好几倍虽然答案通常还是对的因为第一次出队的就是最短的但复杂度和内存都退化了。正确做法是入队时立刻标记。第二种距离数组没初始化。全局数组默认是 0如果你的 dis 用 0 表示“未访问”那起点之外的所有格子一开始就被认为“已访问且距离为 0”BFS 一步都走不动。所以要么用 -1 区分要么老老实实 memset 成无穷大。这个 bug 在本地跑小数据时可能因为内存恰好是干净的而通过一交上去就 WA特别坑。第三种多组数据没清空。有些题目一个测试文件里有多组数据每组都要重新 memset。如果你只 memset 了 dis忘了清空 head/tail或者忘了重置 sx/sy第二组数据直接错乱。我的做法是把所有全局状态的初始化封装成一个init()函数主循环里每组数据开头调一次绝不错漏。第四种边界判断写成了。if (nx 1 || nx n)少了一个第 n 行永远走不到。这种 bug 单步调试很容易发现但如果只靠肉眼看代码有时候真会漏。第五种把字符 1 当成数字 1。有些题目的网格里是数字字符表示代价很多人直接从g[nx][ny]里拿值参与运算忘了减 0。结果代价全部偏大 48答案离谱。6.2 问题速查表现象最可能的原因排查动作答案恒为 -1终点字符没识别到 / 终点被当成障碍打印起点终点坐标确认读入正确答案比正确值大队列没按层扩展 / 距离赋值用了出队时的值检查dis[nx][ny] dis[x][y] 1的位置答案比正确值小起点距离没置 0 / 障碍判断漏了打印完整 dis 矩阵观察形状数组越界崩溃边界判断写在访问数组之后调整判断顺序越界判断放最前大数据 TLE入队未标记导致重复入队把标记移到入队处大数据 MLE队列容量开太大 / dis 用了 int改用一维编码评估 short 可行性多组数据第二组错全局状态没重置抽一个 init 函数统一处理6.3 调试三板斧打印、手推、对拍第一板斧是打印距离矩阵。BFS 跑完后把 dis 按网格格式打出来用 -1 表示不可达。这一步极其有效因为 BFS 的距离场会呈现非常规律的“同心圆”形状一旦你看到某个本该是 2 的位置变成了 5或者出现了一片莫名其妙的 -1问题出在哪个方向立刻就能定位。我基本上每道搜索题都会写这么一段调试代码用完注释掉从不嫌麻烦。第二板斧是手推小数据。构造一个 3×3 或者 4×4 的小网格自己用笔在纸上走一遍记下每个格子的最少步数然后跟程序输出逐个比对。第一个对不上的格子就是 bug 的藏身之处。这个方法比盯着代码看效率高十倍。第三板斧是对拍。写一个暴力版本比如 DFS 枚举所有路径取最小只在小数据上跑再写一个数据生成器随机生成几百组小规模输入两个程序对比输出。一旦发现不一致把那份输入单独存下来分析。对拍能抓到那些你自己想不到的边界情况是赛前必备的手段。注意写对拍的时候暴力版本一定要写对否则会出现“两个都错但错得一样”或者“暴力错了反而显得正解错”的尴尬局面。暴力版本要尽量朴素不要做任何优化宁可慢也要保证逻辑正确。6.4 几个我从实战里攒下来的小技巧技巧一把方向循环展开。如果追求极致常数可以不用 for 循环走方向数组而是写四段重复代码。这样能省掉循环控制开销和数组下标计算编译器也更容易优化。不过我一般只在时限特别紧的时候才这么干因为代码会变丑、变长容易抄错。技巧二用int存坐标而不是pair。手写队列时两个 int 数组比queuepairint,int省内存也省时间因为 pair 会有对齐填充实际占用可能比 8 字节还多。如果进一步压成一维编码id x * (m 1) y队列只要一个 int 数组内存直接减半。技巧三先判断终点再扩展。很多题目终点可能在图的很深处提前判断能省下大量无用的扩展。但要注意判断必须放在出队之后、扩展之前这样保证取到的距离是最小的。技巧四读入用%s而不是逐字符。前面说过%s自动跳过空白不会受换行干扰。但要注意%s会在字符串末尾补\0所以你的数组每行至少要开 m 2 的大小从下标 1 开始写正好给\0留了位置。技巧五下笔前先把变量命名想清楚。sx, sy起点tx, ty终点nx, ny邻居qx, qy队列。这套命名我用了很多年读代码时眼睛一扫就知道是什么不用反复回翻定义。别小看这个比赛时改 bug 的速度很大程度上取决于代码的可读性。7. 我个人在这类题上的几点体会写了这么多版 BFS我最大的感受是模板本身几分钟就能背下来真正耗时间的是那些边角情况。同一个模板换个读入方式、换个边界判断顺序、换个标记时机正确性和效率就完全不同。所以别急着追求“写得快”先把每一行为什么这么写搞清楚。等你把“为什么入队就要标记”“为什么越界判断要在最前面”“为什么提前返回要放在出队时”这三个问题都能不假思索地答出来这道题以及它背后的一整类网格搜索题基本就吃透了。另外还有个习惯我想分享每次写完 BFS我都会刻意造一组“起点就在终点旁边”“起点被障碍包围”“整个图只有起点”这样的小数据跑一遍。这些极端情况往往就是评测数据里的坑点提前自己踩一遍比交上去等反馈要划算得多。踩过的坑越早越好因为同样的坑你不会踩第二次。
