企业官网建设流程全解析

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；向下拨是数字减1，1向下拨回到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，向上拨一格就是数字加1，9要变回1，我习惯写成：

b[i] = b[i] % 9 + 1;

这个式子看起来有点绕，其实相当于把数字范围看成1到9的循环。d为1到8时，d%9还是d，加1得到2到9；d为9时，9%9是0，加1得到1。一行代码完成循环进位。

向下拨一格则是数字减1，1要变回9。我用的公式是：

b[i] = (b[i] + 7) % 9 + 1;

验证一下：d为2时，(2+7)%9+1等于1，正确；d为9时，(9+7)%9+1等于8，正确；d为1时，(1+7)%9+1等于9，正确。这个公式等价于“减1后按1到9循环”。

很多初学者这里会写if判断，当然可以，但公式写熟了以后代码会非常干净。拨动操作一共要生成8个邻居：4个位置，每个位置有向上和向下两种。

交换相邻位就简单了，直接交换数组相邻两位：

swap(b[i], b[i + 1]);

注意i只能取0、1、2，否则i+1会越界。这里是最容易写错的地方之一，后面我会专门列出来。

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)); queue<int> 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)。打个比方，假如 b=8，d=10，单向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的最短距离。初始化时两个维度都置为-1，dist[0][start]=0，dist[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)); queue<int> 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自测，比如起点和目标相同时输出0，1234到1235输出1，1234到2134输出1。这种case一旦出错，基本能定位到状态生成或距离返回的逻辑。

4.4 如何检验双向BFS真的变快了

我学双向BFS的时候有个执念：非要用数据证明它比单向快。最简单的方法是在代码里加一个计数器，每次从队列里取出节点时tot++，最后输出tot的值，对比同一组输入下单向和双向各扩展了多少个节点。

以这题为例，单向BFS最坏情况下几乎要把6561个状态全部扩展一遍，而双向BFS通常会在一两千个状态以内就相遇，差距非常直观。如果你跑出来的tot比单向还多，基本可以断定是“按层扩展”写出了bug，或者方向选择逻辑有问题。

网上有些题解会告诉你双向BFS一定能过、一定快，但自己动手验证一遍，印象会深得多。这也是我刷题时的一个习惯：凡是涉及优化的题目，都要跑个计数器看看优化到底优化在哪。

5. 常见问题与调试心得

5.1 典型问题速查表

这里整理一下我在写这道题时遇到过的典型问题，以及网上学弟学妹们问得比较多的情况。

这张表里的前两行是最容易坑到人的。尤其是不按层扩展的双向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验证，比反复抄模板有用得多。真到了面试或者比赛现场，这个模板能帮你节省下来的时间，远比你当初练它时花掉的时间要多。