今天是打卡信奥刷题系列的第 2858 篇题目是 P4554 小明的游戏。说实话这道题我第一眼看到时是有点不屑的一个棋盘从左上角走到右下角这不就是个 BFS 吗。结果样例一遍过交上去却 WA 得莫名其妙。回头重新读题才发现自己把“代价”和“步数”混为一谈。这道题真正要算的不是你走了多少步而是你跨过了多少次颜色变化。每一步如果目标格子和当前格子颜色一样代价是 0颜色不一样代价才是 1。经典普通 BFS 在这里直接失效正解是 0-1 BFS也就是用双端队列 deque 实现的 BFS 变种。这篇文章适合正在学搜索算法、备战信奥比赛或者想把 BFS 家族彻底搞明白的同学。尤其是你已经刷腻了普通 BFS想进入带权图最短路门槛的这道题是绝佳的跳板。下面我会把题面翻译、0-1 BFS 的原理、完整 C 实现以及调试中容易踩的坑全部讲清楚。1. 先读懂题这不是普通的走迷宫1.1 题面到底问了什么从左上到右下的“变色成本”P4554 小明的游戏题面看起来很简单给一个 n 行 m 列的棋盘每个格子上要么是 0 要么是 1。小明从左上角出发要走到右下角每一步可以往上下左右四个方向移动一格。关键点来了移动的代价不是固定的 1而是取决于两个格子的颜色是否相同颜色相同这一步代价为 0颜色不同这一步代价为 1。最终要求的是从起点到终点的最小总代价。注意起点格子自身的颜色不影响答案代价只产生在移动过程中。也就是说小明可以随便绕路只要绕路能让他少跨几次颜色变化哪怕多走很多步也是值得的。我第一次做这题的时候直接写了一版按步数计数的普通 BFS样例输出碰巧是对的。因为样例里的最优路径恰好也是最短路径所以没暴露问题。但实际测试数据一上来立刻翻车。原因很简单题目要最小化的是“变色次数”不是“路径长度”。这两个目标在很多情况下是冲突的。1.2 为什么普通 BFS 在这里会翻车普通 BFS 之所以能解决迷宫最短路是因为它默认每一步代价都相同队列按层扩展先被搜到的点一定对应最少步数。这个结论成立的前提是“边权全为 1”但在这道题里边权要么是 0 要么是 1普通 BFS 的层序性就被破坏了。我举一个直观的例子假设有一条很长的通道所有格子颜色都是 0从起点到终点可以一路走到底代价是 0但步数可能达到 10。与此同时还有一条短路径只要 3 步就能到达终点但这 3 步里跨越了两次颜色变化总代价是 2。普通 BFS 会先把短路径走完3 步就碰到终点然后输出 2。可正确答案明明是那条需要走 10 步、但代价为 0 的长通道。问题的根源在于普通 BFS 的队列里先出队的点不代表“当前代价最小”只代表“当前步数最少”。当出现 0 代价边时一个代价更小的点可能排在一个代价更大的点后面层次关系完全乱了。所以我们需要一种机制让“代价为 0”的扩展能插队到前面优先被处理。1.3 把棋盘看成带权图既然普通 BFS 不行自然的思路是把问题抽象成图论模型。棋盘上每个格子都是一个节点相邻格子之间有一条无向边。这条边的权值不是 1而是 0 或 1具体看两边格子的颜色是否一样。于是题目就变成了在这个边权只有 0 和 1 的图上求从起点节点到终点节点的最短路。到这里最直接的想法是跑 Dijkstra因为 Dijkstra 能处理任意非负边权。但是再仔细一想Dijkstra 的优先队列维护了太多没必要的信息这个图的边权只有两种取值完全可以用更轻量、更快的算法也就是 0-1 BFS。2. 0-1 BFS 的完整原理为什么一个双端队列就够2.1 双端队列的排序秘密dist 最多只差 10-1 BFS 的核心数据结构是双端队列 deque听起来有点神奇但它背后的逻辑其实非常朴素。回想 Dijkstra 每次都要从优先队列里取出当前距离最小的点这是因为边的权重可能是任意整数你没法预判下一个最小距离是谁。但如果边权只有 0 和 1情况就简单了。假设当前从队列取出的点它的最短距离是 d。通过它扩展邻居时新邻居的距离只可能是 d 或者 d 1。这样一来整个队列里的距离值永远只会出现两种一种是当前正在处理的 d另一种是 d 1。所以我们可以用一个双端队列来模拟优先队列当扩展出一条 0 边时新节点的距离和当前节点相同应该插到队首让它紧跟当前这一层当扩展出一条 1 边时新节点的距离比当前节点大 1应该放到队尾排到 d 1 那一层去。这样不断处理下去队列始终按距离从小到大排列和优先队列的效果完全一致但每次插入和删除都是 O(1) 的。第一次看到这个技巧的时候我总觉得它太“巧”了像是什么特技。后来想明白才觉得它本质上就是把优先队列压缩成了两个桶。因为可能的距离值只有两个优先队列的很多运算都是浪费。2.2 用优先队列是杀鸡用牛刀很多人在没学过 0-1 BFS 之前遇到这道题会直接写堆优化的 Dijkstra写完也能 AC毕竟数据不算极端。但既然题目专门设计了 0 和 1 两种边权就是希望你用更高效的 0-1 BFS。两者对新手的区别不只是常数大小更是对图论算法思想的理解深度。我做一个直白的对比算法适用边权核心数据结构时间复杂度普通 BFS边权全相等普通队列 queueO(V E)0-1 BFS边权只有 0 和 1双端队列 dequeO(V E)Dijkstra任意非负边权优先队列 priority_queueO((V E) log V)在棋盘规模较大的题目里V 是格子数E 大约是 4 倍格子数。0-1 BFS 和普通 BFS 是同阶复杂度但比 Dijkstra 少了一个 log 因子。对信奥题目来说这个差异平时可能看不出来一旦 n、m 到了几千级别log 的差距就会变成实实在在的运行时间差距。更重要的一点是0-1 BFS 不需要额外的 priority_queue 内存开销deque 的操作也更简单直接。我后来做很多迷宫变种题遇到边权为 0/1 的模型第一反应都会是 0-1 BFS而不是直接套 Dijkstra。2.3 0-1 BFS 的适用边界0-1 BFS 并不是万能的它只适用于边权恰好只有 0 和 1 的图。如果图中出现了边权 2 或者更大的值队列里的距离值就不只有两层了双端队列就无法保证有序性这时候只能老老实实走 Dijkstra。还有一点要注意0 边可以出现多个连续所以在 0-1 BFS 里允许存在大量 0 权边连接的“免费区域”。这也是它对比普通 BFS 最强大的地方普通 BFS 不承认免费移动0-1 BFS 则把免费移动优先处理这正好符合这类题目的实际逻辑。判断一道题能不能用 0-1 BFS我一般会问自己三个问题图中边的代价是不是只有两种是不是都是非负的能不能把问题转化成单源最短路如果三个答案都是肯定的那基本就可以确定用 0-1 BFS。3. 完整 C 实现从零写出 AC 代码3.1 输入输出优化与多组数据的处理P4554 的输入格式很典型是多组数据每组先给两个整数 n 和 m如果 n 和 m 同时为 0就代表输入结束。这种格式在信奥题目里非常常见我建议直接写成 while 循环读入判断条件用逗号表达式或者逻辑与都行。先说读入优化。很多人写 C 会无脑 cin遇到大量输入时和 stdio 不同步效率会慢不少。我在代码里第一行就会写ios::sync_with_stdio(false); cin.tie(nullptr);这两行的作用分别是取消 cin 和 C 标准输入输出的同步以及让 cin 不再每次输出时都刷新缓冲区。对多组数据、大量读入的题目来说能明显提速。当然如果你更习惯 scanf也完全没问题。不过要注意不要混用 cin 和 scanf否则关闭同步后可能出现不可预期的顺序问题。我平时用 VSCode 配置好 C 环境写题直接跑数据很方便。这道题的数据规模下关闭同步的 cin 已经足够快不需要再写快读模板。3.2 方向数组、状态表示与初始化网格题的标配是方向数组四个方向上下左右。我习惯写成两个数组int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};这样写的好处是循环四个方向时代码非常简洁。棋盘存储我用 vector 每一行是一个字符串访问第 x 行第 y 列就是 a[x][y]。距离数组 dist 要初始化成无穷大我用的是 0x3f3f3f3f这个值足够大而且两个 0x3f3f3f3f 相加不会溢出 int。访问标记数组 vis 初始为 false。这里必须注意题目是多组数据每组数据都要重新创建或清空这些数组。我用 vector 动态分配每组数据自动重新初始化这样最省心也避免静态数组残留上一次数据的脏值。3.3 核心 BFS 循环代码下面给出完整的核心实现注释写清楚每一步在干什么#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m (n || m)) { vectorstring a(n); for (int i 0; i n; i) { cin a[i]; } const int INF 0x3f3f3f3f; vectorvectorint dist(n, vectorint(m, INF)); vectorvectorbool vis(n, vectorbool(m, false)); dequepairint, int dq; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; dist[0][0] 0; dq.push_back({0, 0}); while (!dq.empty()) { int x dq.front().first; int y dq.front().second; dq.pop_front(); if (vis[x][y]) { continue; } vis[x][y] true; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) { continue; } int w (a[nx][ny] a[x][y]) ? 0 : 1; int nd dist[x][y] w; if (nd dist[nx][ny]) { dist[nx][ny] nd; if (w 0) { dq.push_front({nx, ny}); } else { dq.push_back({nx, ny}); } } } } cout dist[n - 1][m - 1] \n; } return 0; }注意我在初始化队列时用的是 push_back起点入队。之后每次松弛成功如果边权是 0 就 push_front如果边权是 1 就 push_back。这个顺序千万别搞反否则整个队列的有序性就崩了。如果你在的 OJ 支持 C17可以把取队头的两行改写成结构化绑定auto [x, y] dq.front(); dq.pop_front();但考虑到有些老 OJ 默认标准不是 C17稳妥起见我平时的比赛代码会写成 first 和 second 的方式兼容性最好。3.4 关于 visited 的一个关键细节很多初学者第一次写 0-1 BFS 时会把 vis 标记放在入队的时候类似于普通 BFS 的做法。这是一个很隐蔽的坑。因为 0-1 BFS 中同一个节点很可能先被一条“代价不是最优”的路径入队后来才被另一条“代价更优”的路径再次更新。如果入队时立刻标记 vis那个更优的更新路径就会被拦在门外导致答案偏大。正确做法是出队的时候再检查 vis 和标记这样能保证每个节点第一次出队时拿到的距离已经是最优距离。我在代码里还加了提前结束的优化。因为 0-1 BFS 的出队顺序和 Dijkstra 一样是按距离从小到大排列的所以终点的距离在它第一次出队时就已经确定了。如果想省点时间可以在出队后发现是终点就直接 break。为了代码简洁我上面的版本没有加这个优化但你知道这个原理后可以根据自己习惯选择。4. 踩坑实录与调试心得4.1 队列操作写反0 边放到队尾会怎样这个坑我印象太深了。第一次手写 0-1 BFS 时我把 push_front 和 push_back 写反了结果跑样例依然正确。因为样例规模小恰好没触发错误条件。后来提交到评测系统直接 WA 到怀疑人生。为什么会写反还能过样例呢因为 0-1 BFS 的正确性依赖队列的有序性一旦 0 边放到了队尾那些原本应该优先处理的 0 代价节点就会排到后面整个算法退化成一个不够优的 BFS。在小数据、随机数据上可能碰巧能算出正确答案但构造过的测试数据一上来就露馅。我后来给自己定了一条规矩写完 0-1 BFS先不要急着交而是手动造一个“长通道 0 代价 短路径高代价”的对比数据跑一遍看结果是不是正确的那个最优解。这样能在本地把这类错误直接拦下来。4.2 边界条件与多组数据残留这道题是 while 循环多组输入每次循环结束一定要检查 dist 数组是否被正确地重新初始化。我早期喜欢开静态二维数组然后每组数据手动 memset。看起来没问题但有一次忘记在 continue 分支清零导致上一组的数据污染了下一组的结果。后来我干脆全部改用 vector 动态分配每组数据都重新创建 dist 和 vis。虽然多了一点内存分配的开销但彻底杜绝了残留问题对比赛来说更安全。另外就是坐标边界。我的代码里坐标从 0 开始所以判断越界的条件是 nx 0 || nx n || ny 0 || ny m不要写成 nx n 或者 ny m否则会出现神秘的数组越界和段错误。这类网格题我写多了以后会先把边界条件专注检查一遍再检查核心循环逻辑。4.3 从这题延伸出去的经典变形0-1 BFS 这个模型在信奥和算法竞赛里非常常见。做完 P4554 之后我又陆续碰到过几类经典变形这里简单分享一下。一类是“最小翻转次数”问题比如有一个 01 串每次操作能把某个位置翻转但翻转某些位置的代价可能是 0 或者 1问最小代价达到目标状态。还有一类是带传送门的迷宫传送门的移动代价是 0普通移动代价是 1问从起点到终点的最小代价。这类问题本质都是边权 0/1 的最短路可以无脑套 0-1 BFS。还有一类进阶思路如果图中存在大量连续的 0 边可以把这些 0 边连通的区域先缩成一个点再跑最短路。这样图的规模会大幅缩小运行速度还能进一步提升。这个技巧我是在刷题后期才学到的遇到超大数据范围特别有用。4.4 我的刷题建议如何把一道板子题吃透很多人刷题只是为了 ACAC 完就下一道这样其实效率不高。我的习惯是一道题 AC 之后至少再想三个问题我能把代码里用到的算法原理讲给另一个人听吗这道题我能不能改一改条件比如把边权改成 0/2还能用同样的方法吗有没有比现在实现更简洁的写法就拿 P4554 来说我 AC 之后又专门去挑战了 Dijkstra 版本对比两版代码的运行时间才真正理解了 0-1 BFS 的优势。后来又找了几道类似的迷宫题专门练习 push_front 和 push_back 的选择直到形成肌肉记忆。这种练习方式虽然慢但对算法能力的提升是实打实的。最后再分享一个小技巧手写 0-1 BFS 时可以在队列里存 pairint,int但如果棋盘很大pair 可能稍慢一些。想压常数的同学可以把二维坐标编码成一个整数比如 id x * m y队列里只存 int取出时再解码回 x 和 y。我实测在某些数据比较极限的题目里这个写法能明显降低耗时。这道题不一定要这样写但道理先记在心里以后遇到大数据就能用上。