题库里编号 1996、标签写着 bfs、题面里一个代号 WZK 的旅行者要在一张图或一张地图上跑出最省事的那条路线——这类题我从入门一路写到带新人，见得太多了。它的外壳是"旅游"，内核是广度优先搜索（BFS）求无权图最短路，考的不是你能不能背出模板，而是你能不能把"旅游"这个生活化描述准确翻译成一张状态图，再用最省的方法在图上按层推进。很多人三分钟敲完模板，然后在一个vis标记的位置上卡掉两个小时，最后发现逻辑没错、错在顺序。

这篇东西想解决的就是这类问题：拿到一个"某人要去某个地方、问最少多少步/最少多少花费"的题目，怎么判断该不该用 bfs，状态该怎么定义，队列和去重怎么写才不炸内存不超时，以及提交之后从 WA 到 AC 的那条排查链路该怎么走。适合刚学完 BFS 模板、能默写但一到变形题就发懵的同学，也适合已经能写但对性能细节模棱两可的人。下面所有代码都是 C++，可以直接拿去改。

1. "WZK旅游"这四个字里藏着的信息量

1.1 为什么旅游类题目八成落在最短路模型上

题目管这个叫旅游，本质是在问"从 A 到 B 最少付出多少"。只要题目里出现"最少""最短""最快""至少几次"这类字眼，并且每一次行动的代价是一样的——走一格算一步、坐一趟车算一次、过一个城市算一天——那它就是一个边权全为 1 的图上的最短路问题，标准解法就是广度优先搜索。

这个判断很关键，因为它直接决定了你该不该往 Dijkstra、SPFA、甚至 DP 的方向想。我见过不少人一看到"最短路"三个字就条件反射地写优先队列，代码又长常数又大，其实题目里每条边代价都是 1，用优先队列属于纯纯的自我折磨。BFS 在边权相同的图上能保证"第一次到达某点时的步数就是最小步数"，因为它是一层一层往外扩的，先扩到的一定是层数浅的。

生活化一点说：往平静的水面丢一颗石子，波纹一圈一圈往外推。第一圈到达的地方，一定比第二圈到达的地方近。BFS 就是模拟这个波纹扩散过程，队列就是"这一圈还没处理完的点"。你只要保证波纹不会重复扫同一片水面，整个推进过程就是 O(V+E) 的。

1.2 BFS 能用的三个硬前提，缺一个就白写

我把这三个前提单独拎出来讲，因为它们是你判断"这题能不能用 BFS"的唯一依据，比背模板重要得多。

第一，所有边的代价必须相同（通常是 1）。如果题目里出现"走平地花 1 天、爬山花 3 天"这种差异化代价，普通 BFS 立刻失效，因为你没法保证先出队的节点代价更小。这时候要么把代价拆成多个虚拟节点，要么直接换 0-1 BFS 或 Dijkstra。旅游题特别喜欢加这种设定，读到"某些路需要额外花费"就要立刻警觉。

第二，必须有明确的、可枚举的状态。状态就是你"当前所处的情况"，要能用有限个变量完整描述。网格题里是坐标(x, y)，图论题里是节点编号u，如果题目还有"已经用了几次免费机会""还剩多少油"这类限制，就要把这一维加进状态里。状态定义不全，是 BFS 最隐蔽的错误来源——你的程序会跑得飞快，答案就是不对。

第三，必须能判断"这个状态我来过没有"。重复访问同一个状态，轻则答案变慢，重则死循环。所以一定要有一个vis或者dist数组来记账。很多新手栽在"忘记标记起点"或者"标记写在错误的位置"，后面第 3 节我会专门拆这个坑。

这三条同时满足，BFS 才是安全的。缺任何一条，你写出来的东西可能在小样例上碰巧对，一交大样例就原形毕露。

2. 把题面翻译成状态图：四个必须钉死的要素

2.1 状态到底该存什么

拿到题，第一步不是敲代码，是在纸上写清楚四件事：状态是什么、起点是谁、终点是谁、一步能怎么走。这四件事写不明白，代码写得再漂亮都是碰运气。

先说状态。"WZK 在某座城市"和"WZK 在某张地图的某个格子"，看起来是一回事，落到代码上差别很大。前者状态就是一个整数u，用邻接表存边；后者状态是(x, y)二元组，用方向数组在网格上挪动。这两套写法我下面各给一份模板，别混着用。

再说那些容易被漏掉的附加维度。题目里如果出现下面这些描述，状态就要加一维：

这个表看着简单，但它决定了你的数组开多大、复杂度多少。我见过一道题，加了一维"已用免费次数"之后状态数从 10^5 变成 10^6，数组开小了直接 RE，开大了 MLE，卡在中间的滋味很难受。所以动手之前先算状态总数，这是习惯问题。

2.2 边的权值决定了你用哪种队列

状态和转移定好之后，看每条边的代价。这一步是个分叉口，走错方向后面全错。

代价全是 1，用普通队列queue或者数组模拟队列，最标准的 BFS。 代价只有 0 和 1 两种，用双端队列deque，这就是 0-1 BFS，0 代价的走法塞队首，1 代价的塞队尾，保证队列近似单调。 代价是任意非负整数，老老实实上 Dijkstra，BFS 帮不了你。

旅游题最常出现的变形是第二种：某段路"不花钱""瞬移""免费换乘"，这就是 0 代价边。这时候如果你还用普通队列，程序不会报错，答案会偏大，而且只在大数据上偏，调起来非常恶心。看到"免费""不需花费""直接到达"这类字眼，脑子里就该亮灯。

至于路径连通性怎么表示，网格题用方向数组，图论题用邻接表或前向星。我给的建议是：点数不超过 10^3 用邻接矩阵无所谓，超过就用邻接表，因为邻接矩阵在稠密图上省事但点数一大就爆内存。旅游类题目的地图经常是 n×m 网格，n,m 上千，此时节点数上百万，千万别用二维矩阵建图。

3. 手写队列与去重：BFS 的性能全在这两个地方

3.1 数组模拟队列的写法与容量估算

先给结论：竞赛里写 BFS，我基本不用std::queue，一律数组模拟。原因很实在——std::queue每次push/pop都有函数调用和内存分配的开销，元素多的时候常数能差出两到三倍。而数组模拟队列就是两个下标head、tail在一个静态数组上滑动，读写都在连续内存里，对缓存极其友好。

const int MAXS = 1000005; // 状态总数的上限 int qx[MAXS], qy[MAXS]; // 分别存横纵坐标 int head = 0, tail = 0; qx[tail] = sx; qy[tail] = sy; tail++; // 起点入队 while (head < tail) { int x = qx[head], y = qy[head]; head++; // 出队 // ... 扩展后继状态，然后 qx[tail] = nx; qy[tail] = ny; tail++; }

队列容量怎么估？原则只有一条：队列里最多同时存在"状态总数"这么多个元素，因为每个状态最多入队一次（前提是你正确去重了）。所以MAXS直接开到状态总数就行，别抠抠搜搜开一半。网格题状态总数是n*m，如果地图是 1000×1000，那MAXS就是一千万，两个 int 数组各 40MB，加起来 80MB，已经有点悬了。

这时候有个很实用的技巧：把二元状态压成一个整数。id = x * m + y，队列只存int一个数组，出队时再解回来x = id / m, y = id % m。存储直接减半，而且取模除法的开销远比你想的小。再极端一点，如果n*m不超过 2^31，压成一个 int 完全没问题；我甚至见过有人用位运算(x << 11) | y来压缩，前提是 m 不超过 2048。

3.2 入队标记还是出队标记，这是个送命题

这一小节是我最想强调的地方，因为我见过的 BFS 错误里，一半以上出在这里。

正确的做法是：在节点入队的那一刻就标记它已访问，而不是等它出队再标记。

// 正确写法 while (head < tail) { int u = q[head++]; for (每个后继 v) { if (vis[v]) continue; vis[v] = true; // 入队前就标记 dist[v] = dist[u] + 1; q[tail++] = v; } }

// 错误写法：出队时才标记 while (head < tail) { int u = q[head++]; if (vis[u]) continue; vis[u] = true; // 太晚了 for (每个后继 v) { if (vis[v]) continue; q[tail++] = v; } }

差别在哪？在错误写法里，同一个节点可能被多个不同的前驱重复塞进队列。假设一个格子有四个邻居都能到达它，那它就会被 push 四次，队列规模直接膨胀，极端情况下（比如稠密图）能膨胀到边数级别，复杂度从 O(V+E) 劣化，内存也跟着炸。更麻烦的是这道题如果是多组测试数据，队列数组开得刚刚好，一个膨胀就直接越界 RE。

判断标准很简单：只要你的算法是"层序推进、第一次到达即最优"，标记就必须放在入队处。0-1 BFS 是个例外，它靠dist松弛而不是靠vis，同一个点确实可能多次入队，那是另一套逻辑，别混。

3.3 多组数据下的时间戳去重

旅游类题目很喜欢一个输入里塞多组地图，问你每组的最小步数。这时候每次memset(vis, 0, sizeof(vis))看着没问题，实际上如果vis开了一千万，而每组地图只有 10×10，那你十有八九的时间都花在清空一个根本没用到的巨大数组上。TLE 报出来的时候，你会以为是 BFS 写得慢，其实是 memset 拖的。

解决办法是时间戳标记法：vis数组存整型，不再存 0/1，而是存"这是第几组数据访问的"。

int vis[MAXN][MAXN]; // 全局变量，默认全 0 int stamp = 0; for (int tc = 1; tc <= T; tc++) { stamp++; // 每组数据用一个新时间戳 // 访问判断从 if (vis[nx][ny]) 变成 if (vis[nx][ny] == stamp) // 标记从 vis[nx][ny] = 1 变成 vis[nx][ny] = stamp }

这样就不需要任何清空操作，一组数据一秒钟搞定。距离数组同理，如果题目要输出步数，可以另开一个dist数组并且用同样的时间戳技巧，或者干脆把dist也编码进vis里（用一个足够大的基数，比如vis[id] = stamp * BASE + step，读的时候取模）——不过这种做法可读性差，我不太推荐，除非你被卡得很惨。

注意：时间戳法要求stamp单调递增且不溢出。int上限二十一亿，一般测试组数远达不到，但如果是交互式或者极端的多组（比如十万组），就用long long或者定期重置。

4. 一份可以直接抄的 BFS 骨架（含网格与邻接表两版）

4.1 网格版：旅游地图的标准解法

这是最贴合"旅游"意象的一版。地图上有可走格子和障碍，问从起点到终点最少几步。

#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; int n, m, sx, sy, tx, ty; char g[MAXN][MAXN]; int dist[MAXN][MAXN]; int qid[MAXN * MAXN]; const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; int bfs() { if (sx == tx && sy == ty) return 0; // 起点即终点，别漏 int head = 0, tail = 0; int sid = sx * m + sy; qid[tail++] = sid; dist[sx][sy] = 0; while (head < tail) { int id = qid[head++]; int x = id / m, y = id % m; for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (g[nx][ny] == '#') continue; if (dist[nx][ny] != -1) continue; dist[nx][ny] = dist[x][y] + 1; if (nx == tx && ny == ty) return dist[nx][ny]; qid[tail++] = nx * m + ny; } } return -1; // 不可达 }

几个细节值得单独说。dist初始化为 -1 有两个作用：一是表示"没访问过"，二是让不可达的格子自然区分于步数为 0 的起点。用 0 初始化就会踩到"起点步数也是 0，怎么判断它访问过没有"的坑。起点单独先判一次相等，是因为如果起点等于终点，循环里永远碰不到终点判断（因为起点已经处理完了），会返回 -1。

4.2 邻接表版：城市之间往返的情形

如果题目给的是城市之间的通路，用前向星建图更合适。

const int MAXN = 100005, MAXM = 400005; int head[MAXN], nxt[MAXM], to[MAXM], ecnt = 0; int dist[MAXN], q[MAXN]; void addEdge(int u, int v) { to[ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt++; } int bfs(int s, int t) { fill(dist, dist + MAXN, -1); int h = 0, tl = 0; q[tl++] = s; dist[s] = 0; while (h < tl) { int u = q[h++]; if (u == t) return dist[u]; for (int e = head[u]; e != -1; e = nxt[e]) { int v = to[e]; if (dist[v] != -1) continue; dist[v] = dist[u] + 1; q[tl++] = v; } } return -1; }

注意head数组要初始化为 -1，这是前向星的命门，忘了就是死循环或者越界。另外无向图记得addEdge(u,v)和addEdge(v,u)都要加，旅游题的城市路网基本都是双向的，单向的会特别注明"从 A 到 B 有直达但反方向没有"，读到这种限制要多留个心眼。

4.3 路径还原的最小改动

如果题目不光问最小步数，还要你把路线输出出来，改动其实很小：加一个pre数组，在标记访问的时候顺便记下前驱。

// 在 dist[nx][ny] = dist[x][y] + 1; 之后加一行 pre[nx * m + ny] = id;

最后从终点往回倒推，把路径存进栈里再正序输出。这一步很多人会忘记在"起点直接等于终点"的分支里也要输出一个点，测试数据里经常藏着这种 input。

5. 旅游题的四种常见变种与对应改法

5.1 多源 BFS：不确定从哪儿出发

有时候题目会给出好几个"WZK 可能出发的城市"，问你到某个终点的最省路线；或者反过来，同时求所有点到最近某个特殊点的距离。这时候把所有源点一次性入队，dist全初始化为 0，然后跑一次普通 BFS 就行。

原理很好理解：想象同时往水面丢好几颗石子，波纹互相交汇的地方，就是两个源点的势力范围边界。因为 BFS 是均匀扩散的，谁先扩到就是谁的。这个技巧在"求每个点到最近加油站的距离""求每块陆地到最近的海"这类题目里非常好用，一次 BFS 解决，比每个源点单独跑一遍快了不止一个数量级。

实现上唯一要注意的是：源点集合要去重，如果输入里有重复的起点，老老实实判一下dist是否已经是 0，不然队列会白白膨胀。

5.2 0-1 BFS：当某些路不花代价

旅游题很爱设计"某条高速免费""某段可以瞬移"这种情节。边权变成 0 和 1 两种，就不能用普通队列了，得用双端队列。

deque<int> dq; fill(dist, dist + MAXN, 0x3f3f3f3f); dist[s] = 0; dq.push_front(s); while (!dq.empty()) { int u = dq.front(); dq.pop_front(); for (int e = head[u]; e != -1; e = nxt[e]) { int v = to[e], w = weight[e]; // w 只能是 0 或 1 if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (w == 0) dq.push_front(v); else dq.push_back(v); } } }

它成立的原因在于：双端队列维护了一个"大致有序"的结构，队首附近的距离值小，队尾的大。代价 0 的转移不增加距离，自然应该排在前面优先处理。这个结构保证了每个点第一次被"真正确定"时距离已经最小。

一个常见误解是 0-1 BFS 里也要写vis跳过。其实不需要，靠dist的松弛条件就够了——松弛不成立就不会入队，逻辑自洽。如果你非要加vis，必须保证加在弹出后并且只在第一次弹出时使用，否则会漏掉更优的解。

5.3 分层图与状态压缩：附加维度怎么加

题目如果限制"最多可以免费 k 次"，状态就从u变成(u, c)，其中c是已用次数。这就是分层图，本质是把原来的图复制 k+1 份，第 c 层代表"已用 c 次"。

int dist[MAXN][11]; // 第二维是已用次数，k 通常很小 int q[MAXN * 11]; // 转移时 // 不用免费：从 (u, c) 到 (v, c)，代价 +1 // 用免费：从 (u, c) 到 (v, c+1)，代价 +1（次数这一维不算步数）

数组第二维只开 11，写起来不费劲，但状态总数翻了十倍，队列容量必须跟着放大，这一点极容易忘。

至于"必须收集若干物品"那一类，状态里塞一个二进制掩码，2^m倍，m 一般不超过 10 到 15。这时候再想用二维数组就不现实了，得用map<vector<int>, int>或者把状态编码成u * (1<<m) + mask这种一维整数。编码后的状态空间可能上百万，务必先估内存再动手。

5.4 带必经点的情形：BFS 和状压的结合

更狠的一种问法是"走遍所有景点，最少多少步"。这时候状态是(当前位置, 已访问景点集合)，转移是走到一个还没去过的景点并更新掩码。做法是先用 BFS 算出任意两个关键点（起点、终点、所有景点）之间的距离，再用一个状压 DP 把这些距离串起来。

这个套路值得记住，因为它把一个大问题拆成了两步：BFS 负责"点对点最短路"，状压 DP 负责"访问顺序"。两件事都简单，合起来就能解决一类看起来很难的题。前提是景点数量不多，一般十个左右还能吃得住，超过十五个就要另想办法了。

6. 提交之后：WA、TLE、MLE、RE 的排查顺序

6.1 先怀疑边界，再怀疑逻辑

WA 的时候，我的排查顺序永远是固定的：先把数据范围里最小和最大的边界单独拎出来测一遍。

最小边界包括：起点等于终点（答案是 0 还是 -1？）、地图只有一行或一列、全是障碍、终点点被围死。最大边界包括：n 和 m 都取到上限、所有格子都能走（此时队列会塞满所有点，最容易爆容量）、路径长度接近上限。这几组测完，大部分 WA 的原因就露头了。

然后才是逻辑。逻辑错误里最常见的三个：方向数组写错（有的是四方向写成八方向，有的是dx和dy配错了对）、访问判断漏掉某一维（比如分层图里只判了u没判c）、输出格式不对（多组数据少输出了换行，或者不可达时题面要求输出-1而你输出了0）。

6.2 TLE 的三种成因与卡常手段

TLE 通常来自三类原因，按概率从高到低排：队列膨胀、重复清空、常数太大。

队列膨胀就是前面说的标记位置错了，先回去检查vis标记是不是在入队前。重复清空就是多组数据时memset了一个巨大的数组，改用时间戳。常数太大则是std::queue或者vector的动态扩容造成的，换成静态数组模拟队列。

再往上一层还有几个卡常技巧，我用得比较多：把(x, y)压成一维整数减少访存；把方向数组的循环展开成四段（编译器开-O2一般也会做，但关键题可以手动写）；把if (nx < 0 || nx >= n || ny < 0 || ny >= m)换成在边界外扩一圈哨兵（把地图外围一圈全部标成障碍，这样就不用判越界了，省掉两次比较）。

最后这个哨兵技巧我特别推荐，因为它同时能防住越界 RE。做法是读入地图时坐标从 1 开始，把第 0 行、第 n+1 行、第 0 列、第 m+1 列全部设成不可走，循环里就只剩一句if (g[nx][ny] == '#') continue;，代码短了，也快了。

6.3 RE 与 MLE 的典型触发器

RE 在 BFS 里几乎只有两个来源：队列数组开小了，或者数组下标算错了。

队列开小了最隐蔽，因为小数据全过，大数据一交就炸。判断方法是把MAXS临时开大十倍试试，如果过了，那就是容量问题。下标算错通常是压缩状态时的编码冲突，比如x * m + y里 m 写成了 n，或者没考虑 0 起始和 1 起始的区别。

MLE 则多是局部数组开在栈上导致的。一个int dist[1005][1005]放在函数里就是 4MB，加上几个类似的就超过默认栈限制了，直接段错误。养成习惯：大数组一律开全局，全局变量在静态区，不受栈大小限制。

6.4 一个容易被忽略的点：输入读入方式

地图题里如果用scanf("%c")逐个读字符，换行符会被当成一个格子的内容读进来，整个地图错位一格，然后你调一晚上都找不到问题。解决办法是用scanf("%s")按行读，或者cin >> g[i][j]逐个读（它会自动跳过空白），或者读完整行再逐字符处理。

我自己的习惯是：字符地图一律用scanf("%s", g[i] + 1)，下标从 1 开始，天然避开换行问题，还顺便能用上前面的哨兵技巧。这一条看着不起眼，但它救过的调试时间比任何算法优化都多。

7. 对拍：把"我觉得对"变成"它确实对"

7.1 暴力怎么写

当你的 BFS 交上去一直 WA 而你又看不出问题时，最快的办法不是继续盯代码，是写一个暴力程序。暴力不需要效率，只需要绝对正确且容易验证。

对于求最短步数的题，暴力有几种写法。最朴素的是深搜枚举所有路径取最小值，加上步数上限剪枝；如果图很小，可以用 Floyd 求全源最短路；如果状态空间不大，甚至可以直接做 BFS 但用set存状态，虽然慢但逻辑简单到你不可能写错。

暴力程序的价值在于它是"另一个独立实现"。同一个逻辑用两种方式写，两边同时错的概率远低于一边错。我自己写暴力时故意用完全不同的数据结构，就是为了避免"复制粘贴同一个错误"。

7.2 造数据与对拍脚本

数据生成器我一般用 Python 写，因为随机数的控制比 C++ 顺手。

import random n = random.randint(1, 8) m = random.randint(1, 8) print(n, m) grid = [] for i in range(n): row = ''.join(random.choice('..#') for _ in range(m)) grid.append(row) print('\n'.join(grid)) sx, sy = random.randint(0, n-1), random.randint(0, m-1) tx, ty = random.randint(0, n-1), random.randint(0, m-1) print(sx, sy, tx, ty)

注意生成器里要控制障碍比例，全障碍或者全通路都测不出问题，我一般让#占两成左右。另外起点和终点要允许重合，这是最容易漏测的边界。

对拍脚本用 shell 就行：

while true; do python3 gen.py > in.txt ./bf > out1.txt < in.txt ./std > out2.txt < in.txt if ! diff -q out1.txt out2.txt > /dev/null; then echo "发现差异，输入已保存在 in.txt" break fi done

跑起来之后去泡杯茶，回来看看是不是停在了某组数据上。停下来的那组输入就是你梦寐以求的反例，直接拿去单步调试，通常五分钟内就能定位。

提示：对拍时编译器一定要开-Wall -Wextra，很多未初始化变量和越界隐患编译器会直接告诉你。我有一半的 RE 是被编译警告提前拦下来的。

8. 我自己在这类题上的一些固定习惯

写到最后，分享几个我被坑出来、后来变成肌肉记忆的做法。

第一，写 BFS 前先在纸上画一个小例子，手推一遍队列的变化。三五个节点的图，画出每一层谁先入队谁后入队，这个过程只要两分钟，但能提前发现状态定义是不是漏了维度。我有太多次是敲完代码运行样例对了就交，结果错在状态维度上，回头改要重写一大半。

第二，dist数组的初始值我永远和"不可达"的语义绑定。网格题用 -1，图论题用 0x3f3f3f3f，绝不用 0。用 0 就意味着你得额外维护一个vis，多一个数组就多一处出错的地方。

第三，队列容量宁可开大两个数量级，也别刚好卡着上限。多占的那点内存换来的是一整晚的安心。真遇到内存卡得死的情况，再回过头来做状态压缩。

第四，多组数据的题，第一件事是把初始化写对再写算法。我见过太多人在算法上折腾一小时，最后发现是上一组数据的head、tail没清零。这种错误事后看蠢得不行，但当时就是看不见。

第五，不可达的输出格式一定回题面确认。有的题要求输出-1，有的要求输出No solution，有的要求输出0。这种细节失分最冤，明明算法全对。

这类"某某去旅游求最短路线"的题，模板早就成熟了，真正拉开差距的是你对状态空间的理解和对边界细节的敏感度。把上面几份骨架抄下来改改就能用，但更值钱的是那几条排查顺序，下次卡住的时候按着走一遍，比盯着屏幕发呆有效得多。