1. 先把“旅游”翻译成图论语言BFS 建模的第一步那道编号 1996 的“旅游”题我前后翻来覆去做了三遍第一遍读完题面直接开写交上去错了一半的点第二遍老老实实画图才发现自己把“移动一步”和“到达一个格子”这两件事混为一谈了第三遍才把 BFS 的模板理顺一遍过。这篇就把整个过程拆开讲包括我当时为什么会想歪、模板该怎么搭、哪些地方最容易翻车。核心关键词其实就三个网格地图、最短步数、广度优先搜索BFS。这类标题里带“旅游”“走迷宫”“最少步数”的题目本质上都是同一套东西——把地图抽象成一张无权图每个可走的格子是一个点上下左右相邻能走通的两个格子之间连一条长度为 1 的边然后求起点到终点的最短路径。BFS 在这类问题里的地位相当于泡面里的开水——没有它你也能吃但吃起来就不是那个味儿了。它解决的问题非常明确在所有边权相同通常都是 1的图上求单源最短路径。它的工作方式和往平静水面扔一颗石子一样涟漪从起点一圈一圈往外扩第一圈是距离 1 的所有格子第二圈是距离 2 的所有格子以此类推。因为扩展顺序严格按距离递增所以任何一个格子第一次被访问到时拿到的距离一定就是最短距离不会再有更短的走法在后面出现。这个性质是 BFS 能用来求最短路的根本原因也是它和 DFS 最本质的区别——DFS 只管“能走到”不管“走得近不近”。适合谁来读如果你是刚学完队列和图的存储、正准备刷搜索题的新手这篇可以当模板课来看代码可以直接抄如果你已经能默写 BFS但总在细节上莫名其妙 WA答案错误或者 TLE超时那第 5 节的排查清单可能更对你胃口如果你在准备比赛、需要快速判断一道新题该不该用 BFS、该用什么变体第 4 节的变体对照表应该能帮你省下不少读题时间。我会尽量把每个“为什么这么写”都交代清楚因为这类题目最坑的地方从来不是“BFS 是什么”而是“状态怎么定义”“标记放在哪一行”“边界怎么判”这些看起来琐碎的细节。2. 建模的核心状态设计与搜索空间评估2.1 为什么这道题的“点”不是坐标而是“局面”新手最容易犯的错是把地图上的格子和图论里的点直接画等号。在纯网格最短路里这样没错但“旅游”类题目往往会加一点料有的格子是草地走进去要多花一步有的格子是传送门踩上去会把你弹到另一个位置有的题要求按顺序打卡若干个景点。一旦出现这种附加条件一个坐标就不再足以描述你当前的处境必须把“你在哪”和“你现在的附加状态”打包成一个整体这个整体才是图论意义上的“点”。我给这种打包方式起了个土名字叫“身份证号原则”每个状态都得有一张独一无二的身份证只要两个状态的身份证号不同它们在 BFS 里就是两个不同的点必须分开记录访问标记。举个例子如果题目里有“钥匙”机制那么 (3, 5) 这个位置、手里没钥匙和 (3, 5) 这个位置、手里有钥匙是两个完全不同的状态你不能用一个二维的vis[3][5]把它们混为一谈否则就会出现“拿着钥匙走回原地却被判定为已访问、导致无法推开门”的诡异错误。状态设计做完之后紧接着要评估搜索空间有多大。这一步很多人跳过结果写完跑出来内存爆掉。评估方法很简单把每个维度的取值范围乘起来。假设地图是 n×m附加状态有 k 种那么总状态数是 n×m×kBFS 队列最多同时装下这么多元素vis和dist数组也得开这么大。以常见的 1000×1000 地图为例纯坐标状态是 10^6 个尚在可控范围如果 k 是 4就变成 4×10^6这时候就得开始考虑int数组的内存开销了——一个 4×10^6 的int数组占 16MB两个就 32MB很多老平台的内存限制是 64MB 或 128MB稍不注意就踩线。2.2 边权到底是不是 1一个必须先确认的前提BFS 求最短路的唯一前提是边权相同。这句话我建议你抄在草稿纸最上面因为它是判断“这题能不能直接 BFS”的唯一标准。普通的上下左右移动走一步代价是 1所有边权都是 1放心用 BFS。但如果题目说“进入沼泽格需要额外消耗 2 点体力”那从沼泽相邻格子进沼泽的这条边权值就变成了 2而其他边还是 1这时候 BFS 的“按层扩展”就被破坏了第一次访问到某个点拿到的未必是最短距离。遇到边权不全为 1 的情况通常有三条路可走我在第 4 节会展开这里先给个结论性的判断如果边权只有 0 和 1 两种用双端队列实现的 0-1 BFS复杂度还是 O(VE)比堆优化的 Dijkstra 常数小很多如果边权是任意正整数老老实实上 Dijkstra如果边权种类很少比如只有 1 和 2也可以把一个代价为 2 的格子拆成两个中间节点强行把边权拉回 1继续用普通 BFS。这三种做法各有适用面选错了不一定 WA但很可能 TLE。还有一个隐蔽的坑有些题目表面上边权都是 1但你仔细看会发现“移动到相邻格”和“传送到指定格”这两种操作的代价不一样。这种情况下如果传送操作只在少数几个格子上出现可以整体用 BFS 特殊处理如果传送格遍地都是那就该考虑建分层图了。2.3 建模完成之后该做什么先手算一遍小样例我个人的习惯是状态设计定下来之后不急着写代码先在纸上跑一遍最小的样例。找一个 3×3 或者 4×4 的地图手动用队列模拟 BFS 的扩展过程把每一层的格子标上数字看看扩展顺序对不对、终点是不是在最早的那一层被碰到。这个过程大概花三到五分钟但能提前暴露大概一半的逻辑错误比如方向数组写反、边界判断漏了一侧、起点忘记初始化距离。手算还有一个额外好处它能帮你确认题目的答案是“步数”还是“经过的格子数”。这两个东西在某些题目的定义下差 1我见过太多人代码逻辑完全正确、就因为输出的时候没加或没减这个 1硬生生错掉一半测试点。手动跑一遍样例把样例的输入输出和自己的手算结果对齐这个 1 到底是加还是不加一目了然。3. 模板骨架一份可以反复套用的 BFS 实现3.1 队列、vis、dist 三件套的职责划分一份干净的 BFS 代码骨架永远是三样东西队列、访问标记、距离数组。它们各自的分工必须清楚混用就会出问题。队列负责维护“待扩展的边界”也就是当前这一层以及下一层的候选点vis负责回答“这个点以前有没有进过队列”防止同一个点被反复入队导致队列爆炸dist负责记录“从起点到这个点的最短距离”如果题目只问可达性可以省掉它。关于vis和dist能不能合并我的建议是能合并就合并但要看清楚语义。如果距离数组初始化为 -1那么dist[x][y] ! -1本身就等价于“已访问”一个数组干两件事代码更短也不容易出现两个数组更新不同步的问题。但如果距离的合法取值包含 -1比如某些带负权的特殊题目那就必须分开。合并的时候还要注意初始值的选择memset(dist, -1, sizeof(dist))对int数组是安全的因为 -1 的二进制是全 1但如果用memset给long long数组赋 0x3f 之类的值就得小心字节填充的问题稳妥写法是用fill或者手写循环。3.2 方向数组四方向和八方向的写法取舍网格题的方向扩展我推荐用两个常量数组dx[]和dy[]配合一个循环而不是写四段几乎一样的 if 分支。原因很实际写四段 if 的时候你极有可能在复制粘贴的过程中把某一行的加减号写反而这种错误编译器完全不管只能靠测试数据抓抓不抓得到全看运气。用方向数组就不一样了方向对不对一眼就能看出来改起来也只改一行。四方向的经典写法是const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1};这四组分别对应上、下、左、右。如果你需要八方向含对角线就在后面补上{-1,-1}, {-1,1}, {1,-1}, {1,1}这四组注意顺序要和dy严格对应别错位。有些题目会明确说“只能走上下左右”有些会说“八个方向都能走”读题时务必确认别凭感觉。至于边界的判断有两种风格。一种是在循环内部用 if 判断越界代码直观缺点是每次都要写四个比较。另一种是在网格外面加一圈“围墙”把合法坐标范围从[1,n]×[1,m]扩展成[0,n1]×[0,m1]然后把围墙上的格子预先标记成障碍这样循环内部只判断“是不是障碍”就够了。后一种写法能省掉越界判断常数略小而且能避免“下标为负”这种在某些平台上行为未定义的坑。我个人在数据规模大的时候偏向加围墙规模小的时候怎么顺手怎么来。3.3 入队时标记还是出队时标记一个决定生死的细节这个问题值得单独拎出来说因为它是我见过的最容易写错、而且错了之后症状最迷惑的地方。vis的标记动作必须放在入队的那一刻而不是出队的那一刻。原因在于同一个格子可能被多个不同的前驱节点同时发现。假设格子 C 同时与 A、B 相邻BFS 从 A 和 B 分别扩展到 C如果标记动作放在出队时那么 A 把 C 入队、B 也把 C 入队队列里就出现了两份 C等它们相继出队时才被标记队列的元素数量就会成倍膨胀。在小数据上这顶多让程序慢一点看不出问题但在 10^5 级别的数据上队列可能膨胀到百万级内存直接爆掉或者时间超出限制。入队即标记的写法就干净得多A 发现 C 没被标记立刻标记、记录距离、入队B 再来发现 C 已经被标记直接跳过。全程每个格子最多入队一次队列的最大长度不会超过状态总数。这个细节看似只是挪了一行代码的位置实际上决定了你的程序能不能在数据规模上活下来。提示vis标记、dist赋值、push入队这三件事必须挨在一起写中间不要插入任何其他逻辑否则改代码的时候极容易漏掉其中一个。4. 完整实操从读入到输出的全过程4.1 数据读入与坐标系的统一先讲读入。网格题最常见的两种输入格式一种是一次给一个字符串cin row或者scanf(%s, buf)读进来然后逐字符处理另一种是给 n 行 m 列的字符字符之间可能有空格也可能没有。前一种更快也更省心我一般统一用字符串读入因为字符之间有没有空格、换行是 CRLF 还是 LF这些破事用一次性读字符串的方式都能绕开。如果地图规模到了 10^5 行这种级别cin即使关了同步也可能不够快这时候要么改成scanf(%s)要么写一个快读。我自己的习惯是只要数据规模超过 10^5 个字符就直接上快读或者getchar手写循环省得因为读入拖慢整个程序。坐标系方面我强烈建议从 1 开始编号并把数组开大一圈。这样做的直接好处是判断越界的时候可以用nx 1 || nx n这种形式不会出现下标为 -1 的情况加围墙的写法也更自然围墙正好落在第 0 行、第 n1 行这些位置上。当然从 0 开始编号完全没问题只是下标计算要更小心别在某个地方漏减 1。4.2 一份逐段注释的完整代码下面是我现在打这类题目的通用骨架以“网格最短路、四方向移动、# 为障碍、S 起点、T 终点”为例#include cstdio #include cstring #include queue using namespace std; const int MAXN 1005; int n, m; char g[MAXN][MAXN]; // 地图从 1 开始编号 int dist[MAXN][MAXN]; // -1 表示未访问同时兼作 vis int sx, sy, tx, ty; // 起点与终点坐标 const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; int bfs() { memset(dist, -1, sizeof(dist)); // 全部初始化为未访问 queuepairint, int q; // 队列存坐标 dist[sx][sy] 0; // 起点距离为 0 q.push(make_pair(sx, sy)); // 入队即标记二者不可分 while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); // 终点可以在出队时判断也可以在入队时判断 if (x tx y ty) return dist[x][y]; for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 1 || nx n || ny 1 || ny m) continue; // 越界 if (g[nx][ny] #) continue; // 障碍 if (dist[nx][ny] ! -1) continue; // 已访问 dist[nx][ny] dist[x][y] 1; // 距离递推 q.push(make_pair(nx, ny)); // 标记与入队紧挨着 } } return -1; // 队列空了还没碰到终点说明不可达 }这段代码里有几个地方值得单独说。第一if (x tx y ty) return dist[x][y];放在出队之后是合法的因为出队顺序严格按距离递增第一个出队的终点一定是最短的那条路。如果你想再省一点可以把这个判断挪到入队之后立刻返回效果一样能少一次出队操作。第二g[nx][ny] #这个判断必须放在越界判断之后否则就可能在非法下标上读内存虽然大多数情况下不会崩但这是明显的安全隐患。4.3 参数选择与复杂度的实际感受理论复杂度是 O(n×m)每个格子最多入队一次、出队一次每次出队扫四个方向所以总操作数大约是 4×n×m 加上常数。以 nm1000 为例总共约 400 万次内层循环每次循环里有几个判断和一次可能的入队实测在普通机器上跑完大概几十毫秒完全够用。但“够用”的前提是常数没被放大。如果队列里存的是结构体而不是pair如果每次入队都拷贝一个大对象如果dist数组用vectorvectorint而不是静态数组常数可能翻好几倍。我给个经验值当 n×m 超过 10^6 时把队列元素类型控制在 8 字节以内比如把坐标压成一个整数x * (m1) y把数组开成全局静态数组而不是在函数里动态分配这两条能省下相当可观的时间。数据规模推荐队列元素类型推荐距离数组典型耗时普通机器n×m ≤ 10^4pairint,int函数内vector忽略不计10^4 n×m ≤ 10^6pairint,int全局静态数组10~100 msn×m 10^6压成单个整数全局静态数组100 ms 以上需关注常数5. 变形与延伸题目改一版模板要动哪几刀5.1 常见变体对照表同一道“旅游”题出题人稍微改一改条件BFS 的写法就得跟着调整。我把遇到过的高频变体整理成一张表做题的时候可以先对着表定位再决定改哪里。变体特征状态定义关键改动需要注意纯网格最短路(x, y)无入队即标记带钥匙/门机制(x, y, 钥匙集合)vis多一维钥匙集合用位运算压缩移动有 0 和 1 两种代价(x, y)换成双端队列代价 1 进队尾代价 0 进队头多个起点(x, y)所有起点初始入队起点距离都初始化为 0多个终点(x, y)到达任意终点即返回终点集合预先标记需要记录路径(x, y)额外记每个点的前驱从终点倒推再反转要按顺序经过若干点(x, y, 已过点数)vis多一维状态数等于点数乘格数拿“带钥匙”这个变体举个例子。假设地图上有若干把钥匙和对应的门钥匙可以用一个二进制位表示那么状态就是dist[x][y][mask]其中 mask 是当前手上钥匙的集合。转移的时候如果新格子是钥匙mask 就或上对应的位如果新格子是门只有 mask 里对应的位是 1 才能通过。这种题的状态数直接乘以 2^kk 是钥匙种类数通常 k ≤ 10所以总状态数可控。5.2 边权不为 1 时的三条路前面提过边权不全为 1 是 BFS 的硬伤。这里展开说三条路线的取舍。第一条路是拆点也就是把一个代价为 k 的格子拆成 k 个串联的中间节点中间节点之间用代价 1 的边连接整体边权就拉回 1 了。这条路的最大优势是代码改动极小主循环一行不用动只需要在扩展时多加一层“进入代价格要连续走 k 步”的判断。缺点也很明显如果 k 很大拆出来的节点数会膨胀搜索空间跟着变大。所以这条路适合 k ≤ 3 这种小代价。第二条路是 0-1 BFS用双端队列代替普通队列。核心思想是遇到代价为 0 的边就把新节点塞到队头让它优先被扩展到遇到代价为 1 的边就塞到队尾。这样队列里的元素天然按距离单调不减排列取出来的永远是最小的。代码实现如下dequepairint,int dq; memset(dist, 0x3f, sizeof(dist)); dist[sx][sy] 0; dq.push_front(make_pair(sx, sy)); while (!dq.empty()) { int x dq.front().first, y dq.front().second; dq.pop_front(); 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; int w cost(nx, ny); // 进入该格子的代价0 或 1 if (dist[x][y] w dist[nx][ny]) { dist[nx][ny] dist[x][y] w; if (w 0) dq.push_front(make_pair(nx, ny)); else dq.push_back(make_pair(nx, ny)); } } }注意这里的vis判定方式变了不能简单地用“访问过就跳过”而要用“能不能更新更短距离”。这一点和普通 BFS 差异很大改的时候别照抄模板。第三条路是直接上 Dijkstra用优先队列维护。适用面最广任何正整数边权都能处理代价是常数大、代码长。我的判断标准很简单如果边权种类只有两种且其中一种是 0用 0-1 BFS其他情况一律 Dijkstra不去纠结那点常数。5.3 多源 BFS 与反向 BFS有两个小技巧特别实用但很多模板里没提。多源 BFS是指有多个起点要求每个格子到最近起点的距离。做法简单到有点反直觉把所有起点一次性全部入队距离全部初始化为 0然后照常跑 BFS。正确性在于BFS 的队列本来就是按距离排序的所有距离为 0 的点排在前面扩展出来的距离为 1 的点自然也是全局最近的。反向 BFS是指从终点往起点搜。在无权图里正向反向结果一样看起来没什么用但在两类场景下是救命稻草一是终点只有一个而起点有很多或者起点是一个集合反向搜只需一次 BFS二是需要统计“哪些点能到达终点”时正向搜要跑很多次反向搜一次就够。5.4 路径还原怎么把走过的路记录下来有些题目不只问最短距离还要输出具体走法。做法是额外开一个数组记录每个格子的前驱方向比如from[x][y]存的是“从哪个方向走到 (x, y) 的”。BFS 结束后从终点开始按前驱方向一步步往回退退到起点为止把路径上的坐标收集起来再反转就得到完整路径。这里有个细节如果存在多条最短路径题目可能要求输出字典序最小的那条。这时候方向数组的顺序就变得至关重要必须按题目规定的优先级排列方向比如“上、左、右、下”这种顺序因为 BFS 的扩展顺序直接决定了哪条路径先被记录。我在这上面栽过一回方向数组随手按上下左右写结果要求“字典序最小”的那组数据全错。6. 调试实录那些提交后 WA 和 TLE 的夜晚6.1 高频错误速查表下面这些错误我几乎全犯过整理出来当检查清单用交题之前挨个对一遍能省不少重交次数。症状可能原因排查方法样例过一半测试点错起终点判断位置不对或多加了/少加 1手算样例对齐距离定义全部输出 -1起点或终点字符没读到或坐标搞反了打印读入后的地图和坐标部分数据 TLE标记放在出队时队列膨胀检查push前是否有标记部分数据 MLE数组开太大或状态维度算多了打印最大队列长度段错误数组越界或方向判断顺序写反开启越界检查编译选项某些点距离偏大用了 DFS 思路或边权不为1却用普通 BFS确认所有边权是否相等其中“标记放在出队时”这一条最能迷惑人。因为它在小数据上完全正确样例也能过只有数据规模上去之后才会以 TLE 或 MLE 的形式暴露出来。我当时的排查方式是在程序里加一个计数器统计队列曾经达到的最大长度结果发现它比格子总数大了一个数量级这才意识到问题所在。6.2 手造数据与对拍当样例全过但提交不过的时候最快找出问题的方式是对拍。具体做法是写一份暴力解法比如 DFS 加剪枝或者干脆枚举所有路径再写一个随机数据生成器让两份程序跑同一组数据比较输出。随机数据生成器要覆盖几种边界地图最小1×1、1×2、起点就在终点、终点被完全围死、整张图没有障碍、整张图全是障碍只剩下一条羊肠小道。我一般会把这些极端情况单独写死几组再配合随机生成覆盖率就差不多了。对拍脚本写起来也不复杂用 shell 循环几百次每次生成数据、跑两份程序、比较输出一旦不同就停下来保留数据。这套流程我用了好几年几乎所有难调的搜索题都是靠它定位的。注意对拍之前先确认暴力程序本身是对的否则两份都错、结果一致反而会让你误以为程序没问题。6.3 关于输入输出的几个小陷阱有几个坑和算法无关纯属工程细节。第一多组数据的情况。有些题会连续给好几组数据每组都要重新初始化数组。如果vis或者dist忘了清空第二组数据的答案就会莫名其妙地偏小。稳妥做法是把初始化写在读入之后或者用一个“时间戳”技巧数组里存的是上次访问的组号判断时比较组号是否等于当前组省去每次memset的开销。第二输出格式。有的题要求行末不能有多余空格有的题要求每组数据之间空一行这些格式问题经常导致“答案完全正确却判错”。交题之前把输出语句再核对一遍比调试算法省事多了。第三字符读入的坑。scanf(%c)会把换行符也读进来导致地图错位用scanf(%s)就没这个问题。如果一定要逐字符读记得在读之前把空白字符吃掉。6.4 我个人的几条实操体会第一先把状态定义写在纸上再写代码。我现在遇到任何搜索题都会先在草稿纸上写一行“状态 (x, y, 附加维度)”然后估算状态数最后才动手。这个习惯让我少写了无数份白写的代码。第二不要迷信模板。模板能帮你省下打字时间但它不会帮你判断这道题该不该用双端队列、该不该多开一维。真正决定成败的是建模那一步代码只是把建模翻译出来而已。第三测数据要测“丑”的。漂亮的数据测不出问题随机生成的地图往往一片开阔、四通八达恰好避开了所有边界情况。自己造几条全是死路的、起点被围住的、终点在角落的往往一测就现原形。第四时间允许的话把复杂度算清楚再交。我见过太多人因为“感觉能过”就交了结果 TLE 之后反复优化常数其实只要换个算法就能过。花两分钟算一下状态数和操作数比优化半小时常数划算得多。这类题目做多了你会发现真正变化的只有“状态怎么定义”和“边权是不是 1”这两件事剩下的队列、标记、距离递推几乎是肌肉记忆。把模板吃透、把状态设计想清楚剩下的就是熟练度问题。