★ FEATURED ARTICLE 说实话能坚持把备赛周期拉到第八天的人已经不多了。前面七天我们过完了枚举、模拟、前缀和、DFS这些基础板块今天轮到蓝桥杯里另一个躲不掉的名字——BFS。不管你是想冲省一还是只想在省赛里多拿两道题的分广度优先搜索都是性价比极高的一块阵地。它没有动态规划那么玄也没有图论那么多前置知识但它出现的频率一点都不低而且经常以你没见过的样子藏在题干里。我今天不打算给你铺一堆概念想把第八天真正该做的几件事讲透BFS模板怎么写到不用过脑子从“坐标迷宫”到“状态图”的思维转弯在哪里以及0-1 BFS、多源BFS、双向BFS这几个进阶变体到底在什么题目里用得上。适合的读者很明确就是正在冲刺蓝桥杯、已经有一点编程基础但还没系统梳理过BFS的人。当然如果你只是来查漏补缺也会有不少收获。1. 第八天之前你已经为BFS攒下了哪些底子1.1 前面七天的基本盘蓝桥杯的备赛节奏前一周其实都是在给搜索打地基。第一天到第三天通常是枚举和模拟这两块帮我们建立“把题目描述翻译成代码”的直觉第四天到第五天会碰DFS递归、回溯、剪枝这些概念在这个阶段初步成型第六天到第七天开始接触数据结构和基础图论队列、栈、邻接表、连通块的思路逐渐进入视野。这些看起来跟BFS关系不大但等到真正写广度优先搜索时你会发现它其实是“队列这种数据结构 分层扩展的思想 状态判重”的组合。前面几天里最关键的伏笔有两个一是你会用DFS做连通块计数这就帮你理解了“遍历状态空间”这件事二是你写递归时养成了“先处理边界条件、再处理转移”的习惯这在BFS里同样重要。还有一个容易被忽略的底子是“调试能力”。前七天的模拟题和DFS题会逼着你学会打印中间变量、单步跟踪递归过程。到了BFS调试难度其实更大因为队列里同时存在很多层的数据一旦判重写错程序会陷入死循环或者答案完全对不上。如果你没有前期的调试经验今天会走得比较痛苦。1.2 BFS在整个竞赛策略里的地位你可能已经发现了蓝桥杯的题目风格很“现实”它不会在题干里直接写“请使用广度优先搜索”而是把搜索问题包装成一个模拟过程。比如“小明从左上角走到右下角最少需要多少步”“要把所有苹果都变成腐烂状态需要几分钟”——这类描述本质上就是BFS。从省赛的题型分布看搜索类题目加在一起通常能占到两三道以上而BFS又以它“求最短/最少/最早”的特性成为其中出镜率最高的模型。更关键的是BFS的代码量不大套路固定一旦你练熟了属于“考场上的稳定得分点”。相比动态规划的复杂状态设计BFS的思维方式更机械这对竞赛经验没那么多的选手来说是非常友好的。但这里也必须提醒一句BFS的入门门槛低不代表拿分容易。出题人惯用的手段是增加状态维度、改变扩展方式、增加边权或者让起点不止一个。如果你只会在字符矩阵上数最短步数那今天的内容才算正式开始。1.3 第八天的目标要具体化既然已经到了冲刺阶段就不能再抱着“把这章知识看一遍”的心态。第八天你只需要锁定三个具体目标第一把最朴素的BFS模板打到肌肉记忆程度拿到任何“最短步数”问题能五分钟内敲出框架第二理解BFS真正的运行机制——为什么队列能保证第一次出队就是最短距离第三掌握三到四种常见变形至少见到题目能识别出“这是BFS变体”。明确目标的好处是你不会在某个冷门的优化技巧里陷太深。蓝桥杯冲刺不是搞学术研究而是要在有限时间内拿到能拿的分数。所以今天这篇文章里的每个知识点我都会从“考场上怎么用”的角度去讲而不是单纯罗列原理。2. 先把最经典的网格BFS模板写进肌肉记忆2.1 五件套队列、距离数组、方向数组、边界判断、分层扩展网格BFS可以说是所有变体的母版。就算你已经会写了我还是建议你找一道最普通的迷宫题对着下面这个框架重新过一遍脑子因为它包含了你在所有BFS题里都会用到的五个要素。队列存放待扩展的节点也就是“当前这层已经被发现但还没往外走一步”的点。距离数组既记录从起点到当前点的步数又承担判重的职责。方向数组用两个定长数组表示上下左右四个方向的坐标偏移。边界判断每次扩展新坐标前先检查是否越界、是否为障碍物。分层扩展每次从队头取出一个节点尝试向四个方向走一步满足条件的节点入队距离加一。这里面最容易出错的是方向数组的配对。我见过太多人把dx和dy写反导致程序一直原地打转或者走斜对角。推荐写法是用int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1};顺序上严格对应上右下左这样即使忘了一个方向也方便对着坐标轴检查。2.2 为什么dist数组可以同时当答案表和判重表很多刚开始学BFS的人会困惑为什么不能单独用一个vis数组来过再弄一个step数组来记录步数答案是可以但没必要。因为BFS是按层扩展的从起点出发第一次到达某个点时所用的步数一定是最短步数。既然如此我们完全可以用距离数组初始化成-1表示“还没访问过”一旦被赋值就表示“已经访问过并且记录下了最短距离”。这样做的额外好处是你最后不需要单独维护“几个箱子都到手了”之类的复杂路径信息直接让距离数组和判重逻辑合为一体。等你写到多源BFS或者0-1 BFS时会越发觉得这个设计很省事。需要注意的一点是在某些题目里同一个物理格子可能因为其他条件不同而属于不同的“状态”此时单纯在坐标维度上判重就不够了。这个我们放到第三章详细说但你现在先记住一个原则BFS判重的最小单位永远是你问题定义中的独立状态而不是天然坐标。2.3 一套能直接跑的C模板下面这个模板是蓝桥杯环境下最稳妥的版本不依赖C17的结构化绑定也不依赖任何冷门头文件。#include bits/stdc.h using namespace std; const int MAXN 55; char mp[MAXN][MAXN]; int dist[MAXN][MAXN]; int n, m, sx, sy, ex, ey; int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; int bfs() { memset(dist, -1, sizeof(dist)); queuepairint, int q; q.push(make_pair(sx, sy)); dist[sx][sy] 0; while (!q.empty()) { pairint, int cur q.front(); q.pop(); int x cur.first, y cur.second; if (x ex y ey) return dist[x][y]; for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 || nx n || ny 0 || ny m) continue; if (mp[nx][ny] #) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push(make_pair(nx, ny)); } } return -1; }这个模板有几点你可以试着改造成自己的习惯比如把pairint, int换成一个结构体Node在结构体里多存一个step字段。这样可以帮助你理解“队列节点里到底该装哪些信息”这件事。但真到了比赛我反而建议用dist数组存距离因为少维护一个字段就少一份出错的风险。3. 从“格子”到“状态图”BFS最容易被卡住的三个转弯3.1 转弯一状态不只是坐标如果你只把BFS理解成“在二维数组上广度扩展”那做题范围会被卡得很死。真正的竞赛BFS扩展的是一个“状态”。所谓状态就是能唯一确定当前局面的一组变量。我举一个很典型的例子。某个题说“有一个四位密码锁每个数字可以向上拨或向下拨一位最少转几次能从0000到9527”——这种题里状态是四位数本身不是某个坐标。再比如“有四个箱子排成一排每次只能移动一个1号箱子到相邻空格子目标状态是让它们按顺序排列”——状态是整个排列而不是某个棋子坐标。一旦你把状态当成BFS的节点那么“扩展”的定义就从“上下左右走一格”变成了“对当前状态施加一次合法操作生成下一个状态”。搜索的路径长度就是操作次数目标就是看谁能最早到达目标状态。这也解释了为什么很多搜索题看起来完全不像迷宫却依然是BFS。你只要在草稿纸上把“状态节点”画出来把“操作”看成“边”它本质上就回到了你熟悉的那个东西上。3.2 转弯二判重的对象是“状态”而不是“坐标”这是初学者最容易翻车的地方。如果题目里只有一个人在迷宫走那么状态就是坐标vis[x][y]没问题。可一旦角色变成两个、三个或者携带了不同的钥匙、血量、剩余步数单纯记录“人在哪儿”就不够了。举一个实际点的例子一个迷宫里有钥匙和锁人走到某个格子的距离可能因为“有没有拿到钥匙”而不同。同一个格子没钥匙时是绝路有钥匙时却能继续走。如果你的访问数组只记录坐标第一次到达该格子时还没钥匙把它标记为访问过之后你拿到钥匙再回来就会发现进不去了得到错误答案。正确的做法是把所有“会对后续决策产生影响的要素”都编进状态里。状态可能是(x, y, keyMask)表示“位置加上当前已持有钥匙的集合”。判重数组就得开到vis[x][y][1keyNum]这一维度。很多选手在这一步不是不会写而是压根没意识到需要这样去思考。3.3 转弯三队列节点到底该放多少信息队列节点的信息设计是算法有风险和代码复杂度之间的平衡。你当然可以把全部状态信息都放进节点里比如坐标、步数、血量、钥匙集合、当前方向但这样做的代价是队列里的每个元素都很大。我的经验是凡是能从数组里取出来的信息就不要塞进队列节点。步数可以用dist[state]取方向如果只影响下一步移动也可以编码进状态里。队列里只放“定位这个状态所必需的最小信息组合”。比如普通迷宫只放坐标带钥匙的迷宫放坐标和钥匙掩码。这样做的原因是调试的时候你能一眼看出队列里存的东西是什么。我见过一个选手把步数放在节点里去重数组却用vis[x][y]结果同一个格子被压进去很多次但每次步数不同导致有些路径被错误剪枝——这类问题如果节点里只放位置就根本不会出现。4. 打开队列的另一个抽屉0-1 BFS与多源BFS4.1 0-1 BFS当边权只有0和1用双端队列替代堆蓝桥杯有种常见的套路给你一个迷宫大多数移动花费1步但某些特殊操作花费0步。比如“走到传送门上可以瞬移到另一个传送门”或者“按下某个按钮不需要时间”。遇到这种边权只有0和1的图直接写Dijkstra也能过但它多了一个log的复杂度写起来也更重。正确的做法是用双端队列。0-1 BFS的核心思想是如果一条边的代价为0那么这个新状态的距离和当前状态相等它应该被放到队首优先被扩展如果一条边的代价为1那么这个新状态的距离是当前距离1它应该被放到队尾按正常BFS的顺序扩展。因为代价只可能是0和1所以队列里的距离值始终只有两个连续层次队头元素一定是对应着当前最小距离的状态。这里有个关键点0-1 BFS里的判重不能用“第一次入队即最短”的朴素BFS思维因为有些状态第一次被扩展时可能是从一条代价较大的路径到达的后续还可能通过代价为0的路径更新成更短距离。所以你在实现Dijkstra时怎么更新距离在0-1 BFS里就怎么更新距离只是把优先队列换成了双端队列复杂度降了一档。我写一个最小框架看清楚这个更新逻辑const int INF 0x3f3f3f3f; vectorint dist(N, INF); dequeint dq; dist[start] 0; dq.push_back(start); while (!dq.empty()) { int u dq.front(); dq.pop_front(); for (auto e : adj[u]) { int v e.first, w e.second; if (dist[v] dist[u] w) { dist[v] dist[u] w; if (w 0) dq.push_front(v); else dq.push_back(v); } } }如果你只会在网格里上下左右走这道题可能用不上但一旦遇到“走楼梯/坐电梯/传送门”这类描述它就特别好使。4.2 多源BFS多个起点同时蔓延就是另类最短时间多源BFS的原理其实很直白BFS不是只能从一个起点开始。你可以在一开始就把所有起点都压入队列它们的初始距离都设为0。这样整个图会像水波一样从多个中心同时向外扩散每个格子首次被访问到的时间就是它距离最近的那个起点的距离。经典的“腐烂橘子”问题就是这么干的题意是橘子矩阵里有一些已经开始腐烂的橘子每分钟腐烂会向上下左右蔓延一格问多少分钟全部腐烂。你只要把所有腐烂橘子当成起点去做BFS答案就是整个距离数组里的最大值。多源BFS在蓝桥杯里还有一个更隐蔽的变体“多个救援队和多个火灾点同时移动问那个位置能最早被救援队到达而火还没到”。这种题你甚至可以分别做两次BFS一次从火源算每个格子的火到达时间一次从救援队算到达时间然后逐格比较。实现上要注意初始入队时所有起点的dist都是0而且不能漏掉任何一个起点。漏一个起点意味着从它出发的那一大片区域全都会算错。调试的时候最常翻车的就是这里因为人很难肉眼看出哪个起点没压进去。我建议你直接在初始化循环里加一个调试输出把实际入队的起点打印出来。4.3 两个变种如何组合使用有时候题目会同时要求多源和0-1边权。比如“多个入口、某些路径是免费通道求到所有目标点的最小代价”。这时你只需要把多个起点都初始化到队列里然后按照边权是0还是1来决定push_front还是push_back。这个组合其实不难真正难的是你愿不愿意把两个模型同时装进脑子里。很多同学遇到“多点特殊通道”的题第一反应是跑N次Dijkstra看到数据范围稍微大一点就TLE。其实只要识别出“多源”和“01边权”这两个关键特征代码量反而比朴素做法更短。这里再补充一句这里的“多源”也可以理解成“把所有可能成为起点的东西一起当作层次0”搜索的对称性会天然帮我们完成比较。5. 双向BFS搜索规模减半的魔法及其前提5.1 双向BFS能行得通的条件大多数选手第一次听说双向BFS是在八数码题里。它的思路也堪称经典既然我们知道起点和目标状态为什么不从两个方向同时扩展到中间汇合搜索树的宽度会因此大幅减小。在二维网格里从起点搜到目标假设每层平均分支数是B最短距离是D单向BFS扩展的节点数大约是B^D量级。双向BFS则可以让正向和反向各扩展约D/2层总节点数约为2*B^(D/2)。当D比较大或者B比较大的时候这个差距是指数级的。但是要用双向BFS有个死前提状态转移必须可逆。也就是说知道自己是从哪个状态来的同时也能从这个状态反向变回去。比如八数码里空格可以上下左右移动反过来自然也行但有些题目的操作函数是不可逆的——把一个数减半的操作不能简单地用乘2回去因为奇偶性会造成信息丢失。这种题就不能用双向BFS。5.2 实现上的三个细节第一个细节是访问标记要区分方向。通常用两个map或两个vis数组正向扩展时标记为1反向扩展时标记为2。当扩展出来的新状态在另一个方向已经被标记时就说明两条搜索路径相遇了此时答案就是正向步数加反向步数再加一。第二个细节是交替扩展而不是死板地正反各一步。更通用的做法是“哪一方向的队列更小就扩展哪一方”。这样能保证两边搜索树的规模尽量平衡避免某一方向爆炸式增长。第三个细节是查找相遇时要对“当前正在扩展的这一层”做完整的检查。简单的写法是写一个expand(当前方向, 扩展一层)的函数见人就在函数内部判断是否碰到另一方向的标记。5.3 什么时候不该用双向BFS蓝桥杯的题尤其是省赛其实不会为双向BFS特意出题。这更多是一种“会了更好不会也不致命”的技巧。所以我不建议你在双向BFS上花太多时间敲实现先理解为什么能减少搜索规模更关键。真正要警惕的是“把双向BFS用歪了”的情况。有一种题目叫目标状态不明确的搜索比如“走到任意出口即可”这种你就没法从终点反向搜。还有一类题虽然目标状态明确但反向转移规则很复杂写反向函数的难度比写正向还大强行搞双向BFS反而浪费时间。冲刺阶段的时间很值钱选技巧的标准是“能稳定拿分”而不是“显得高级”。6. 模拟实战三道题从读题到AC的完整推理链6.1 迷宫最短步数双重循环出口判断先来一道热身题。题意很简单一个NxM的字符矩阵S是起点E是终点#是障碍.可以走问从S到E的步数。这道题就是第二章模板的复现我重点说下推理过程而不是直接贴代码。读题后先判断这是无权图求最短路径BFS合适。再确认状态这个人只在迷宫上走没有钥匙、没有不同速度所以状态就是二维坐标。判重用一个二维数组。虽然题目简单但压力测试时我建议你把起点周围四个点的情况都考虑一遍特别是当起点和终点相邻时答案应该是1而不是0很多人在边界值上翻车。另外提醒一下终点不需要入队。当你从队列里取出终点时直接返回它的距离即可这能省掉一点点时间。别小看这个写法它可以防止你犯另一个错误在入队时统一判断“如果新节点是终点就返回”有的人在初始化时把起点也当成了终点于是输出0浪费一整题。6.2 滑块拼图状态压缩的反向BFS第二个例子是某年模拟赛里出现过的一个滑块题。说有一个3x3的棋盘8个滑块和一个空格空格可以跟相邻滑块交换位置给定一个初始局面问移动到目标局面最少多少步。这道题如果按照“坐标状态”去做状态空间会爆炸因为每个滑块的坐标都会变。正确建模是用一个长度9的字符串表示整个局面空格所在位置也可以包含在里面。每次扩展就是找到空格下标尝试与上下左右交换。判断是否为目标局面直接比较字符串就好了。这里有两个竞赛常用技巧值得说。第一判重可以开一个mapstring, int或者用unordered_map把局面字符串映射到步数。第二如果题目有多次询问都是从不同初始局面出发最后移动到同一个目标那么我们可以只做一次从目标局面的反向BFS预先打出所有状态到目标的距离表之后每次询问直接查表。这就是反向BFS的典型用法。实现反向BFS的关键是反向扩展函数正向是“空格与相邻滑块交换”反向操作完全一样因为交换是可逆的。你只需要把初始状态设成目标局面搜索目标是读入的初始局面。当搜索到某个局面时距离就是答案。这类题写起来比看起来更长但逻辑并不复杂核心在于你愿不愿意把一个局面当成一个节点去思考。6.3 带传送门的迷宫零代价边的00-1 BFS实践第三道题有一个典型的外观“迷宫里有若干个传送门每个传送门都会在脚下激活可以把人传送到另一个指定的传送门传送不消耗步数而往上下左右走一步消耗1步。求从起点到终点的最小步数。”这道题如果按普通BFS做队列里距离相同但路径不同的点没法处理“传送要不要先走过去触发”的问题而传送代价是0和普通移动代价是1并存所以就非常适合0-1 BFS。你可以把“传送门A到传送门B”看成一条边权为0的有向边普通移动看成边权为1的边。写代码时的坑在于传送门的“激活”往往意味着要先站到传送门上也就是说你走到A这一步已经花费了步数再通过A去B才是不花步数。因此0边权应该定义成“从A到B的传送过程”而不是“从某普通点到B的传送”。我见过不少同学把传送当成从任意点都能触发结果答案偏小就是这么来的。这道题如果套用第4章的框架区别只在建图方式每个格子连向相邻的可走格子边权1每个传送门A连向对应的传送门B边权0。然后从起点跑0-1 BFS即可。跑完后检查终点的dist值是不是INF如果是就说明不可达。7. 冲刺阶段BFS常见报错与细节7.1 多组测试数据的边界污染蓝桥杯的不少题目会包含多组测试数据尤其是那种“每个样例给你一个N和M”的形式。最典型的错误是上一组数据BFS结束后队列里残留了节点但dist数组没有重新初始化下一组数据一开始就把上一组的信息当成当前层信息导致答案乱七八糟。解决办法并不复杂在每次BFS开始前清空队列重置dist和必要的vis。我自己的习惯是把BFS写成独立函数所有全局变量在函数内部初始化这样就不会出现“上一次调用污染下一次”的问题。这里有一个细节queue没有clear()你要么声明一个局部队列每次调用自动析构要么用一个while(!q.empty()) q.pop();手动清空。局部队列是最省心的。7.2 访问标记的位置与时机另一个高频报错是“超时”甚至“内存爆炸”原因通常是标记访问的时机不对。BFS中当一个节点被压入队列的瞬间就应该立刻标记访问而不是等它出队时再标记。原因是如果出队时才标记同一个状态的多个副本可能已经被不同路径都压入队列队列里会积攒大量重复节点搜索空间迅速膨胀。不过这个规则在0-1 BFS里要稍微打个折扣因为0权边可能导致一个状态先以较大距离入队后来又出现更小距离需要更新距离。这时候就不能用简单的“入队即标记”要用“比较距离是否更优”来更新。遇到这种情况你别慌它只是从朴素BFS的“不复入队”变成了“距离更小才入队”逻辑上仍然清晰。7.3 别把数组维度开错蓝桥杯数据范围通常不会太大但维度开错会直接数组越界而且排查起来很折磨人。写二维BFS时我建议把行和列的最大值分别定义成常量不要都写成同一个MAXN。比如地图的行是N、列是M两种都可能不同用同一个常量很容易出现行越界但代码不崩溃的情况因为C越界访问是未定义行为有时候碰巧能跑。还有一个内存小技巧如果地图不大距离数组用short也能存但为了保险还是用int更稳。蓝桥杯的内存限制一般够用没必要为了省一点空间把自己搞得提心吊胆。但是如果你用JavaScript或者Python要额外注意算法效率和递归深度好在这儿的BFS不需要递归基本问题不大。7.4 状态编码时的位运算陷阱当你做状态压缩BFS时最容易出问题的是位运算优先级和掩码位对齐。比如用keyMask表示已收集的钥匙集合时更新状态要写成newMask mask | (1 keyIndex)如果有多个钥匙则要分别检查否则会丢失其中一把钥匙的状态。这种错误在题面复杂时很难肉眼发现。我的建议是把“状态转移”单独抽成一个函数函数里只做一件事给定当前状态和操作返回新的状态。这样你可以在本地写一组小数据逐个打印状态转移后的结果确认位运算符合预期后再跑全量。碰上状态压缩题花十分钟做这一步远比在全部数据中Debug半天要划算。7.5 路径输出也是一种常规需求有些题不只要求最短步数还要求输出路径。这时你需要在每次成功入队时记录该节点是由哪个节点扩展来的用一个pre数组保存前驱坐标。等到目标节点第一次被访问到就从终点沿前驱链回溯到起点再把链反转输出。注意如果状态是字符串或更复杂的结构pre数组会比较占空间。此时可以在递归输出中跟着pre走需要留意别因为DFS回溯太深导致栈溢出。蓝桥杯一般不会把这个作为核心考点但你会写的话能多捞一道小问的分数。写在最后的几个BFS判断口诀到了第八天我自己的感受是BFS的代码并不难难的是在考场上快速判断“这道题能不能用BFS、状态到底是什么、边权是否是统一的1”。如果你时间有限就把下面几句话记住题干中出现“最短、最少、最早、至少需要几步”且状态转移可枚举优先考虑BFS转移代价只有0和1时用双端队列多个起点时把起点全部入队目标状态明确且转移可逆再考虑双向BFS。我今天准备的这些内容本质上是把冲刺阶段最该会的BFS模型都过了一遍。可能有些地方你需要自己打开编辑器把模板敲一遍才能体会到里面的细节。开始敲吧第八天的收获取决于你到底动手写了多少行代码。
阅读完成 · 觉得有帮助？
