双向广搜实战：HDU 1195密码锁与BFS搜索优化解析-北京尧图网络

hdu 1195 Open the Lock一道被无数搜索入门文章翻来覆去讲的老题但能真正把双向广搜bbfs讲透的并不多。这题说的是一个四位密码锁给你初始密码和目标密码密码锁的每一位都是1到9每次操作只有两件事要么把某一位向上或向下拨动一位要么把相邻两个位置的数字交换问从初始状态到目标状态最少需要操作几次。问题本身不复杂但它背后其实是标准的无权图最短路径模型非常适合拿来理解BFS更关键的是拿它来吃透双向广搜的完整套路。如果你正在练搜索或者刷题时看到“双向广搜”这个词总是一知半解这道题值得从头到尾好好走一遍。很多人做这道题的时候第一反应是“四位密码状态这么少直接BFS不就行了”。确实单向BFS也能AC但标题里特意标了bbfs说明它的训练重点就是双向广搜。这篇东西我打算按从易到难的顺序写先拆题目再给出单向BFS的常规解法然后解释双向BFS为什么能快、快在哪最后给出可以直接AC的双向BFS完整实现以及我在实际调试中踩过的一些坑。1. 题目拆解密码锁背后到底在问什么1.1 操作模型与状态定义先把题面翻译成算法语言。四位密码锁每一位取值是1到9那么这个游戏的所有局面就是所有由1到9组成的四位数。每一次操作有两种类型第一种是拨动某一位。选定四个位置中的任意一个把这一位向上拨一格或者向下拨一格。向上拨的意思是数字加1但要循环9向上拨回到1向下拨是数字减11向下拨回到9。比如当前是1234如果向上拨第4位得到1235如果向下拨第2位得到1134。这里有一个很容易忽略的点拨动操作是对每一位独立生效的一次操作只改变一位不是整体旋转。第二种是交换相邻位置。四位密码在锁具上是排成一排的所以可以交换第1位和第2位或者第2位和第3位或者第3位和第4位一共三种交换方式。不能交换第1位和第4位因为它们不相邻。每次交换操作也计为一步。把这两个操作当成“边的生成规则”那么每一个四位数就是一个节点每个节点最多能生成11个邻居4位各自向上拨是4个向下拨是4个相邻交换是3个。题目要求的就是从起点四位数到终点四位数的“最少操作次数”换句话说就是这张无权图上两个节点之间的最短路径长度。这里要特别说一句容易把问题想成“每个节点往下扩展一棵树”其实不是树是图。因为操作是可逆的比如向上拨一位再向下拨一位又回到了原状态这就形成了环。所以搜索过程中必须判重不然会无限循环。1.2 状态空间有多大计算一下状态总数。每一位有9种可能四位一共是 9^4 6561 种状态。注意这个数不是10000因为每一位只取1到9不含0。当然代码里开一个10000大小的数组做判重也完全没问题多出来的空间只是浪费一点点内存不影响正确性。6561这个数字看起来很小但搜索题的复杂度不能只看状态总数还要看分支因子和路径深度。每个节点最多有11个分支最坏情况下目标状态的深度未必小。用单向BFS跑最坏就是把6561个状态全部扩展一遍每个状态生成11个邻居也就是大约7万次状态转移在OJ上就是毫秒级的事情。所以这道题严格来说单向BFS的难度并不高。那为什么还要练双向广搜因为6561只是这道题的状态规模换成其他问题比如八数码、十五数码、魔方还原状态空间是百万级、亿级甚至更大的单向BFS会非常吃力。而双向BFS处理的正是“已知起点和终点、求最短路径”这一类问题它能从两端同时推进把指数级增长的搜索深度砍半。Open the Lock 的模型简单、转移清晰是练双向BFS最好的脚手架。2. 单向BFS先跑通最常规的解法2.1 用int编码状态而不是string写搜索第一步要解决的是“状态怎么存”。很多人习惯用string存四位密码写起来直观但有一点不好判重数组不好开用map又慢代码还啰嗦。我建议直接用int编码把1234这个状态就存成整数1234。这样就需要两个互相配合的函数一个是把int拆成4位数字数组另一个是把4位数字数组拼回int。这是整个代码的地基拆装逻辑写错了后面全崩。int getNum(int a[]) { return a[0] * 1000 a[1] * 100 a[2] * 10 a[3]; } void getArr(int x, int a[]) { a[0] x / 1000; a[1] x / 100 % 10; a[2] x / 10 % 10; a[3] x % 10; }之所以把这两个函数单独拎出来是因为BFS过程中反复用到“当前int状态 - 操作 - 新int状态”的转换。用int的好处有两个一是判重数组可以直接开dist[10000]用状态本身当下标O(1) 访问二是队列里存int比存string省内存、省拷贝时间在大状态空间的题目里这些细节会放大成显著差距。2.2 两种操作的实现细节有了数组表示操作就很好写了。先看拨动。假设当前某一位是d向上拨一格就是数字加19要变回1我习惯写成b[i] b[i] % 9 1;这个式子看起来有点绕其实相当于把数字范围看成1到9的循环。d为1到8时d%9还是d加1得到2到9d为9时9%9是0加1得到1。一行代码完成循环进位。向下拨一格则是数字减11要变回9。我用的公式是b[i] (b[i] 7) % 9 1;验证一下d为2时(27)%91等于1正确d为9时(97)%91等于8正确d为1时(17)%91等于9正确。这个公式等价于“减1后按1到9循环”。很多初学者这里会写if判断当然可以但公式写熟了以后代码会非常干净。拨动操作一共要生成8个邻居4个位置每个位置有向上和向下两种。交换相邻位就简单了直接交换数组相邻两位swap(b[i], b[i 1]);注意i只能取0、1、2否则i1会越界。这里是最容易写错的地方之一后面我会专门列出来。2.3 单向BFS的完整AC代码下面给出完整的单向BFS解法。dist数组初始化为-1表示未访问dist的值表示从起点到该状态的最短操作次数。BFS按层扩展第一次遇到目标状态时dist就是答案。#include bits/stdc.h using namespace std; int dist[10000]; int getNum(int a[]) { return a[0] * 1000 a[1] * 100 a[2] * 10 a[3]; } void getArr(int x, int a[]) { a[0] x / 1000; a[1] x / 100 % 10; a[2] x / 10 % 10; a[3] x % 10; } int bfs(int start, int target) { if (start target) return 0; memset(dist, -1, sizeof(dist)); queueint q; q.push(start); dist[start] 0; while (!q.empty()) { int cur q.front(); q.pop(); int a[4], b[4]; getArr(cur, a); int nexts[11], cnt 0; // 生成所有合法邻居 for (int i 0; i 4; i) { // 向上拨 memcpy(b, a, sizeof(b)); b[i] b[i] % 9 1; nexts[cnt] getNum(b); // 向下拨 memcpy(b, a, sizeof(b)); b[i] (b[i] 7) % 9 1; nexts[cnt] getNum(b); } // 交换相邻位 for (int i 0; i 3; i) { memcpy(b, a, sizeof(b)); swap(b[i], b[i 1]); nexts[cnt] getNum(b); } for (int i 0; i cnt; i) { int nxt nexts[i]; if (dist[nxt] ! -1) continue; dist[nxt] dist[cur] 1; if (nxt target) return dist[nxt]; q.push(nxt); } } return -1; } int main() { int T; scanf(%d, T); while (T--) { int start, target; scanf(%d%d, start, target); printf(%d\n, bfs(start, target)); } return 0; }这段代码在HDU 1195上是能直接AC的。但我想强调一点单向BFS能过这题不代表你不需要学双向BFS。这道题的数据量比较小所以优化前后的体感差别不大但如果你以后遇到状态空间大的题目单向BFS可能在扩展几万甚至几百万个节点之后才反应过来到那时候再来现学双向BFS就晚了。3. 双向BFS的优化原理为什么能快这么多3.1 搜索树爆炸式增长带来的思考先理解BFS为什么慢。BFS搜索的过程很像水面波纹向外扩散从起点开始每一步都把当前层的所有邻居扩展出来。假设每一步平均有b个分支要搜索到深度d单向BFS大约需要扩展 b^d 量级的节点。分支因子b越大、目标深度d越深节点数量增长越快这就是“搜索树的指数爆炸”。双向BFS的思路很直接既然起点和终点都知道为什么非要一头扎到底干脆让两个方向同时扩散。从起点出发扩展约d/2层从终点出发也扩展约d/2层只要两个方向的扩散范围碰到一起就找到了一条从起点到终点的路径。这种做法的节点量级大约变成 2 * b^(d/2)。打个比方假如 b8d10单向BFS需要扩展约10亿级别的节点双向BFS两个方向各扩展到第5层总共只要约4万个节点。这个差距是几万倍量级的相当夸张。就算在Open the Lock这种小状态图上双向BFS扩展的总节点数也会明显少于单向BFS虽然绝对时间差不多但思路本身的价值远大于这一题的胜负。3.2 两个方向同时扩展的核心逻辑实现双向BFS先要明确几个部件。在两个方向各准备一个队列队列0从起点开始往后扩展队列1从终点开始往前扩展。注意“往前扩展”在无权图里和“往后”没有区别因为所有操作是可逆的从终点反向走一步等价于从终点的某个邻居走向终点。这也是BFS能在无向图上双向推进的前提。判重和距离也要分成两套。我用的是dist[2][10000]dist[0][x] 表示从起点到状态x的最短距离dist[1][x] 表示从终点到状态x的最短距离。初始化时两个维度都置为-1dist[0][start]0dist[1][target]0。每次循环选一个方向进行扩展扩展出来的新状态如果在另一个方向已经被访问过就说明两个方向的搜索前沿相遇了答案就是当前方向的距离加上另一个方向已经记录的距离。这个判断往往让第一次写双向BFS的人感到别扭但多写几次就会发现它其实非常自然。3.3 按层扩展双向BFS最容易写错的地方双向BFS有一个非常关键的细节每次必须扩展“一整层”不是扩展一个节点。原理在于BFS保证最短性的前提是按层推进。如果双向BFS每次只从某个队列里弹出一个节点处理两个方向的深度就会失衡先碰到的“相遇点”未必对应最短路径可能只是某条较长的路径先被找到。我在初学的时候犯过这个错误代码跑出来答案偶尔偏大而且不是固定偏大是看数据碰运气。后来才明白必须用层循环控制扩展范围。在代码里就是先记录当前队列的size然后只从队列中取size个节点处理这size个节点属于同一层处理完这一层之后新加入的节点归入下一层不会在这一轮被误处理。还有一种常见写法是两个方向交替各扩展一层那也能保证最短性。我个人的习惯是“每次选队列节点数较少的方向扩展一层”这样能让两个方向的搜索范围保持大体均衡总扩展量通常会比固定交替少一些。原理不复杂两个方向谁的节点多谁的下一次扩展就会产生更多新节点让节点少的那边多走走整体更省。4. 双向BFS实战从框架到AC代码4.1 数据结构设计与初始化双向BFS的代码其实只比单向BFS多了一个队列和一套dist数组核心模板可以固定下来。先把需要用到的状态生成逻辑抽成一个独立的函数这样主循环里只需要调一次代码会清爽很多。int generateNext(int cur, int nexts[]) { int a[4], b[4], cnt 0; getArr(cur, a); for (int i 0; i 4; i) { memcpy(b, a, sizeof(b)); b[i] b[i] % 9 1; nexts[cnt] getNum(b); memcpy(b, a, sizeof(b)); b[i] (b[i] 7) % 9 1; nexts[cnt] getNum(b); } for (int i 0; i 3; i) { memcpy(b, a, sizeof(b)); swap(b[i], b[i 1]); nexts[cnt] getNum(b); } return cnt; }这个函数一次生成最多11个邻居返回实际生成的个数。主循环里只需要准备一个int nexts[11]的数组来接结果。初始化部分有一个我踩过的坑每次输入一组新数据dist数组必须重新初始化为-1而且两个维度都要清。如果你在写多组数据的题目时忘了这一步不同case之间的距离信息会相互污染样例可能碰巧能过但提交后各种离奇WA都会冒出来。4.2 主循环与相遇判断主循环的框架如下两个队列都不为空时继续循环选择节点数较少的方向取出该方向的当前层的所有节点逐个生成邻居如果邻居在当前方向没访问过就标记距离再检查对面方向是否已经访问过这个邻居访问过就返回两边距离之和。这里有一个容易引发困惑的点为什么返回的是dist[dir][nxt] dist[other][nxt]而不是把两边都加1因为新状态nxt还没有入队dist[dir][nxt] 已经被赋值为 dist[dir][cur]1它代表从起点/终点到nxt的实际步数dist[other][nxt] 是另一个方向已经算好的实际步数。两个数相加就是经过nxt连通的完整路径长度不需要额外加1。还要注意循环条件必须是两个队列都非空才能继续。如果其中一个方向把能扩展的状态都扩展完了还没相遇说明图不连通。本题的图是连通的但在模板里保留这个判断会更严谨。4.3 完整双广AC代码下面给出我最终提交用的双向BFS完整代码亲测HDU 1195可以直接AC。#include bits/stdc.h using namespace std; int dist[2][10000]; int getNum(int a[]) { return a[0] * 1000 a[1] * 100 a[2] * 10 a[3]; } void getArr(int x, int a[]) { a[0] x / 1000; a[1] x / 100 % 10; a[2] x / 10 % 10; a[3] x % 10; } int generateNext(int cur, int nexts[]) { int a[4], b[4], cnt 0; getArr(cur, a); for (int i 0; i 4; i) { memcpy(b, a, sizeof(b)); b[i] b[i] % 9 1; nexts[cnt] getNum(b); memcpy(b, a, sizeof(b)); b[i] (b[i] 7) % 9 1; nexts[cnt] getNum(b); } for (int i 0; i 3; i) { memcpy(b, a, sizeof(b)); swap(b[i], b[i 1]); nexts[cnt] getNum(b); } return cnt; } int dbfs(int start, int target) { if (start target) return 0; memset(dist, -1, sizeof(dist)); queueint q[2]; q[0].push(start); dist[0][start] 0; q[1].push(target); dist[1][target] 0; int nexts[11]; while (!q[0].empty() !q[1].empty()) { int dir q[0].size() q[1].size() ? 0 : 1; int other 1 - dir; for (int sz q[dir].size(); sz 0; sz--) { int cur q[dir].front(); q[dir].pop(); int cnt generateNext(cur, nexts); for (int i 0; i cnt; i) { int nxt nexts[i]; if (dist[dir][nxt] ! -1) continue; dist[dir][nxt] dist[dir][cur] 1; if (dist[other][nxt] ! -1) { return dist[dir][nxt] dist[other][nxt]; } q[dir].push(nxt); } } } return -1; } int main() { int T; scanf(%d, T); while (T--) { int start, target; scanf(%d%d, start, target); printf(%d\n, dbfs(start, target)); } return 0; }代码写完后我习惯先用几个能心算验证的case自测比如起点和目标相同时输出01234到1235输出11234到2134输出1。这种case一旦出错基本能定位到状态生成或距离返回的逻辑。4.4 如何检验双向BFS真的变快了我学双向BFS的时候有个执念非要用数据证明它比单向快。最简单的方法是在代码里加一个计数器每次从队列里取出节点时tot最后输出tot的值对比同一组输入下单向和双向各扩展了多少个节点。以这题为例单向BFS最坏情况下几乎要把6561个状态全部扩展一遍而双向BFS通常会在一两千个状态以内就相遇差距非常直观。如果你跑出来的tot比单向还多基本可以断定是“按层扩展”写出了bug或者方向选择逻辑有问题。网上有些题解会告诉你双向BFS一定能过、一定快但自己动手验证一遍印象会深得多。这也是我刷题时的一个习惯凡是涉及优化的题目都要跑个计数器看看优化到底优化在哪。5. 常见问题与调试心得5.1 典型问题速查表这里整理一下我在写这道题时遇到过的典型问题以及网上学弟学妹们问得比较多的情况。现象可能原因解决办法输入起点等于终点时答案不对没有在BFS入口特判start target进入BFS后第一行就判断相等直接返回0双向BFS答案比实际大没有按层扩展两个方向深度不同步先遇到非最优路径改成每次扩展完整一层的循环一次只处理当前层节点答案总是差一点或完全不对上下拨公式写反或者把“交换相邻位”写成了任意交换用固定case验证1234上拨最后一位必须得到1235数组越界交换循环写成 i 4导致访问 b[4]交换相邻位循环只到 i 3多组数据WAdist数组没有在每组数据前重置每组数据bfs前都执行 memset(dist, -1, sizeof(dist))运行超时用string存状态且用map判重常数过大换成int编码加静态数组判重这张表里的前两行是最容易坑到人的。尤其是不按层扩展的双向BFS它的错误非常隐蔽因为大多数随机数据下答案是对的只有构造特殊数据时才会暴露。遇到这种情况建议打印两个方向每次扩展的层数看看是否出现某一方向连续扩展了好几层而另一个方向没动静的情况。5.2 几个值得养成的调试习惯第一所有涉及状态转换的函数先单独测试。getNum和getArr配合使用要能还原原状态generateNext生成的数量必须是11个这是两个硬性指标。我见过有人把memcpy(b, a, sizeof(b))错写成memcpy(b, a, sizeof(a))虽然在本机碰巧能跑但换一个编译器或平台就可能出问题因为sizeof(b)和sizeof(a)在大多数情况下都是16字节但一旦数组定义成指针就会翻车。第二BFS层数边界要心里有数。这题状态数只有6561如果某个case跑出来的步数超过6561那一定有bug因为一条最短路径不可能经过同一个状态两次。这个“步数上界”在调试时是个很好的合理性检验。第三多组数据的题目建议每组都输出一下调试信息不要只在最后统一输出。尤其是T比较大的时候前面某组的错误结果会影响你对后面数据的判断。第四操作生成用固定数组而不是vector。vector当然也能用但在这种状态生成极其频繁的题目里固定数组少了很多动态分配的开销代码也更容易控制内存。比赛里vector导致的TLE我至少见过十次以上。5.3 通用模板迁移这道题的双向BFS模板稍加改动就能迁移到很多其他题目上。我最常用的做法是把“状态编码/解码”和“邻居生成”这两个部分独立出来然后主循环保持不变。换一道题只需要改这两个函数以及调整dist数组的大小。比如状态是一个排列的题目可以用康托展开把排列映射成整数状态是9宫格或15宫格可以把格子拼成一个int或者把整个局面hash成一个数字。主循环里的“选方向、扩展一层、判断相遇”三段逻辑完全不用动。这也是我强烈建议把这题模板背下来的原因它解决的从来不只是这一道题而是一整类“已知起点和终点求最短路径”的问题。往深了说双向BFS还可以和折半搜索、迭代加深、A-star等思路结合。A-star需要设计一个可采纳的启发式函数在这题里可以用当前状态和目标状态对应位不同的个数做估计但实现复杂度会高不少。从练手的性价比来看双向BFS是最容易掌握、收益又高的一招。我个人在实际刷题中最大的体会是写双向BFS时不要贪快把“层”和“方向”这两个概念先在草稿纸上理清楚再动键盘。很多人一看模板短就背背完一遇到变种就懵根源就是没理解为什么要按层扩展、为什么相遇时要返回两边距离之和。把这题从头到尾手写一遍再跑几个case验证比反复抄模板有用得多。真到了面试或者比赛现场这个模板能帮你节省下来的时间远比你当初练它时花掉的时间要多。

双向广搜实战：HDU 1195密码锁与BFS搜索优化解析

相关推荐

Agent-Reach：打造能真正触达外部世界的AI智能体架构与实践

Scala类型参数化实战：从泛型到类型类，打造通用数据访问层

OpenShell 实战：跨平台终端命令统一层的设计与踩坑指南

更多资讯

二级公共基础知识10分选择题备考：考点分布、PDF刷题法与避坑指南

华为云ECS部署Oracle RAC 11.2.0.4实战指南

H3模型轻量化实战：DMAD蒸馏+LoRA角色注入

DMAD蒸馏+LoRA角色微调：轻量H3模型实战指南

MindIR导出踩坑指南：MindSpore静态图语法限制与排查技巧

SAP PS模块快速指南：从项目定义到WBS的落地实践

今日更新

Multisim仿真NE555 PWM控制器：从搭电路到调占空比全流程

S32K312 AUTOSAR BSW开发实战：从配置踩坑到烧录交付

双目视觉三维人脸重建：从视差图到点云粗配准全流程解析

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？