简介这是一份面向Java初学者与算法学习者的八数码问题宽度优先搜索实现资源聚焦经典AI搜索问题——3×3滑动拼图的最短路径求解。资源以Java语言编写借助队列存储待扩展状态、哈希表去重完整呈现从状态表示、邻居生成到路径回溯的BFS核心流程适合用于算法课程实验、数据结构练习及面试准备。压缩包共19个文件约29KB包含3个java源码文件、3个class编译文件、4个xml与4个properties配置项以及jar包、manifest清单和说明文档覆盖源码、构建配置与可执行产物便于直接运行与二次修改。目前已有2037人学习下载读者可从中掌握BFS求解八数码的完整思路、状态去重技巧与Java工程组织方式并借助现成代码快速验证与调试自己的搜索算法实现。1. 八数码问题宽度优先搜索从状态空间到 Java 落地的完整拆解八数码问题8-Puzzle是很多算法课和笔试里绕不开的经典搜索题3×3 棋盘上放着 1 到 8 八个数字和一个空格每次只能把空格上下左右相邻的数字滑进来问从初始局面到目标局面最少要走多少步。它看起来简单但状态空间有 9!/2 181440 个可达状态手推几步就乱靠人脑枚举基本是玄学。宽度优先搜索BFS恰好是这类「每步代价相同、求最短路径」问题的标准解法而 Java 实现又能把队列、哈希去重、状态编码这些工程细节一次性讲透。这份资源就是围绕八数码的 BFS 求解展开的 Java 实现适合正在刷算法题、准备机试或者想搞懂「搜索算法怎么从伪代码变成能跑的程序」的开发者。下面我按自己拆项目的顺序把状态表示、判重、扩展、路径还原和性能边界一层层说清楚。2. 状态表示与判重BFS 能不能跑起来的关键八数码的 BFS 写不出来十有八九不是搜索逻辑错而是状态表示和判重没设计好。棋盘状态怎么存、怎么快速判断「这个局面我见过没有」直接决定程序是秒出结果还是跑到内存爆掉。2.1 用一维数组还是字符串表示状态最直观的表示是二维数组int[3][3]但它在入队、比较、哈希时都很别扭。常见做法是压成一维用长度为 9 的数组或字符串空格用 0 表示。比如目标状态1 2 3 4 5 6 7 8 0就存成123456780。// 用字符串表示状态空格记为 0 // 目标状态固定为 123456780 static final String TARGET 123456780; // 一维下标转二维坐标idx / 3 是行idx % 3 是列 static int rowOf(int idx) { return idx / 3; } static int colOf(int idx) { return idx % 3; }用字符串的好处是equals和hashCode都是现成的直接丢进HashSet就能判重不用自己写比较逻辑。代价是每次扩展状态都要做字符串拼接状态多的时候会有一定开销。如果追求性能可以改用int编码把 9 个数字按位压进一个整数判重时用boolean[]或位图速度会快不少。但对入门和大多数机试场景字符串版本足够清晰也够快。2.2 判重为什么必须做不做会怎样BFS 是按层扩展的如果不判重同一个局面会被从不同路径反复入队。八数码的状态图里有大量环比如空格左右横跳就能无限产生新节点队列会指数级膨胀程序要么卡死要么 OOM。所以判重不是优化是正确性的一部分。判重的核心数据结构是「已访问集合」。每从队列取出一个状态先看它是否在集合里扩展出的新状态如果没访问过才入队并标记。这里有个容易翻车的点标记时机。正确做法是入队时就标记而不是出队时才标记。否则同一层里多个父节点可能扩展出同一个子状态导致重复入队。QueueString queue new LinkedList(); SetString visited new HashSet(); queue.offer(start); visited.add(start); // 入队即标记别等到出队 while (!queue.isEmpty()) { String cur queue.poll(); if (cur.equals(TARGET)) { // 找到目标后续做路径还原 break; } for (String next : expand(cur)) { if (!visited.contains(next)) { visited.add(next); queue.offer(next); } } }expand负责把当前状态里空格上下左右能换的位置都换一遍生成合法的新状态。注意边界空格在第一行就不能再往上在最后一列就不能往右越界判断漏一个就会数组越界或者生成非法状态。2.3 状态扩展的边界处理扩展逻辑本身不复杂但边界条件是 bug 高发区。空格的位置决定了它能往哪几个方向走四个方向都要单独判断。static ListString expand(String state) { ListString result new ArrayList(); int zero state.indexOf(0); int r rowOf(zero), c colOf(zero); // 上下左右四个方向用偏移量表示 int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int[] d : dirs) { int nr r d[0], nc c d[1]; if (nr 0 || nr 2 || nc 0 || nc 2) continue; // 越界跳过 char[] arr state.toCharArray(); int nIdx nr * 3 nc; // 交换空格和目标位置 arr[zero] arr[nIdx]; arr[nIdx] 0; result.add(new String(arr)); } return result; }dirs数组把四个方向的坐标偏移写在一起比写四段 if 清爽。nr、nc是空格移动后的新坐标越界就continue。交换时先转char[]改完再转回字符串避免频繁创建中间对象。这段代码看着简单但zero的重新计算、nIdx的换算任何一个写错都会导致状态错乱建议写完先拿几个手工能推的局面验证。3. 路径还原与步数统计从「能不能解」到「怎么解」BFS 找到目标状态只完成了一半实际使用中我们往往还需要知道「最短步数是多少」以及「具体怎么走」。这就需要在搜索过程中记录父节点和移动方向最后回溯出完整路径。3.1 用父节点映射还原移动序列只统计步数的话可以在队列里存「状态 步数」的二元组或者按层计数。但要还原路径就得记录每个状态是从哪个状态、朝哪个方向走过来的。常见做法是用两个Map一个存父状态一个存移动方向。MapString, String parent new HashMap(); // 子状态 - 父状态 MapString, Character move new HashMap(); // 子状态 - 移动方向 // 扩展时记录来源 for (String next : expand(cur)) { if (!visited.contains(next)) { visited.add(next); parent.put(next, cur); move.put(next, dirChar); // U D L R queue.offer(next); } }dirChar根据方向偏移生成比如{-1,0}对应U。找到目标后从TARGET开始沿parent往回走把move里的方向收集起来再反转就是完整的移动序列。ListCharacter path new ArrayList(); String node TARGET; while (parent.containsKey(node)) { path.add(move.get(node)); node parent.get(node); } Collections.reverse(path); System.out.println(最短步数: path.size()); System.out.println(移动序列: path);这里有个细节parent里不包含起始状态所以循环条件用parent.containsKey(node)正好在回到起点时停止。反转后得到的序列是从起点到目标的顺序步数就是序列长度。3.2 步数统计的两种写法与取舍如果只关心最短步数不关心路径可以省掉parent和move改用按层扩展。每处理完一层步数加一。int steps 0; while (!queue.isEmpty()) { int size queue.size(); // 当前层的节点数 for (int i 0; i size; i) { String cur queue.poll(); if (cur.equals(TARGET)) { System.out.println(最短步数: steps); return; } for (String next : expand(cur)) { if (!visited.contains(next)) { visited.add(next); queue.offer(next); } } } steps; // 一层处理完步数加一 }size在循环开始前固定住保证只处理当前层的节点新入队的属于下一层。这种写法内存占用更小但拿不到具体路径。实际做题时如果题目只问步数就用这种问路径就用父节点映射别为了省事两种混着写容易把层数算错。3.3 无解情况的判断八数码不是所有初始局面都能到达目标。判断有无解用逆序数把状态按一维展开忽略空格数前面比后面大的数字对个数。逆序数为偶数则有解奇数则无解。BFS 本身也能「判断」——队列空了还没找到就是无解但那样要遍历完整个状态空间浪费时间。常见做法是入口先算一次逆序数无解直接返回。static boolean solvable(String state) { int inv 0; char[] arr state.replace(0, ).toCharArray(); for (int i 0; i arr.length; i) for (int j i 1; j arr.length; j) if (arr[i] arr[j]) inv; return inv % 2 0; }目标状态123456780的逆序数是 0偶数所以初始状态逆序数为偶数才有解。这个判断在 BFS 之前做一次能挡掉一批注定跑不出结果的输入。4. 避坑与排查八数码 BFS 最容易翻车的五个地方这段是我自己踩过、也看别人踩过的坑按「现象 → 原因 → 解决」整理照着排查基本能覆盖九成问题。4.1 程序跑很久不出结果现象小规模输入秒出稍微复杂一点的局面跑几分钟没反应内存持续上涨。原因判重没生效或者标记时机错了导致同一状态反复入队队列爆炸。解决检查visited.add是否在queue.offer之前执行确认expand生成的状态确实被visited.contains拦住了。可以在循环里打印队列大小正常应该稳定在几万以内如果一直涨就是判重漏了。4.2 结果步数比正确答案多现象能跑出结果但步数比标准答案大。原因按层计数时steps的位置放错或者把起始状态也算成了一步。解决确认steps初始为 0每处理完一整层再加一起始状态在steps0时检查如果起点就是目标答案应该是 0 而不是 1。4.3 数组越界或状态里出现重复数字现象抛ArrayIndexOutOfBoundsException或者生成的状态里数字重复、空格消失。原因expand里坐标换算写错交换时把两个位置搞混或者越界判断漏了某个方向。解决把rowOf、colOf和nIdx nr * 3 nc单独拿出来单元测试用几个已知坐标验证交换逻辑写成「先存临时变量再赋值」别用一行异或交换容易看花眼。4.4 无解输入把程序拖死现象某些输入永远跑不出结果也不报错。原因初始局面本身无解BFS 遍历完整个状态空间才停。解决入口先算逆序数奇数直接返回「无解」别让 BFS 白跑。这一步能省掉大量无效计算。4.5 字符串拼接导致性能差现象逻辑都对但状态一多就慢CPU 占用高。原因expand里频繁toCharArray和new String加上HashSet的哈希开销。解决状态量大时改用int编码 boolean[]判重或者用StringBuilder复用缓冲区。机试场景一般不用优化到这步但要知道瓶颈在哪。5. 进阶技巧双向 BFS 与状态编码优化单问 BFS 能解决八数码但状态空间大时它还是慢。真正让性能上一个台阶的是双向 BFS 和整数编码这两个技巧我在实际跑复杂局面时基本都会用上。5.1 双向 BFS 把搜索空间砍一半单向 BFS 从起点一层层往外扩最坏情况要摸到 18 万状态。双向 BFS 同时从起点和终点扩展两边在中间相遇就停。理论上搜索深度减半实际状态数能降一个数量级。// 双向 BFS 骨架两个队列、两个 visited QueueString q1 new LinkedList(), q2 new LinkedList(); SetString v1 new HashSet(), v2 new HashSet(); q1.offer(start); v1.add(start); q2.offer(TARGET); v2.add(TARGET); while (!q1.isEmpty() !q2.isEmpty()) { // 每轮选较小的队列扩展平衡两边 if (q1.size() q2.size()) { QueueString tq q1; q1 q2; q2 tq; SetString tv v1; v1 v2; v2 tv; } int size q1.size(); for (int i 0; i size; i) { String cur q1.poll(); for (String next : expand(cur)) { if (v2.contains(next)) { // 两边相遇合并步数即为最短 return; } if (!v1.contains(next)) { v1.add(next); q1.offer(next); } } } }关键点是每轮扩展前比较两个队列大小优先扩小的那边避免一边跑太远。相遇判断放在扩展新状态时只要新状态出现在另一边的visited里就说明找到了最短路径。步数统计要分别记录两边的层数相遇时相加。5.2 整数编码与位运算判重字符串状态在双向 BFS 里开销更明显因为要同时维护两个HashSet。把状态压成int能显著提速每个数字占 4 位9 个数字正好 36 位塞进long或int用int需要 4 位 × 9 36 位超出 32 位所以用long更稳。// 把 123456780 编码成 long每个数字占 4 位 static long encode(String s) { long code 0; for (int i 0; i 9; i) { code (code 4) | (s.charAt(i) - 0); } return code; }判重时用HashSetLong替代HashSetString哈希和比较都快得多。如果状态范围可控还能用boolean[]做位图但八数码的编码空间是 9! 级别位图太稀疏还是HashSet更实际。解码时按 4 位一组取出来还原成字符串或数组用于扩展。5.3 一个验证习惯我每次写完八数码 BFS都会固定跑三组用例一组起点即目标答案 0一组一步可达答案 1一组经典复杂局面比如123456780反过来打乱几步。三组都过基本能确认判重、扩展、步数统计三条链路没问题。从那以后我每次写搜索类代码都强制先跑「平凡用例 边界用例 复杂用例」这三板斧比事后 debug 省太多时间。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/15 13:12:36 · 阅读 1.2k 八数码问题BFS算法详解：Java实现与性能优化
简介这是一份面向Java初学者与算法学习者的八数码问题宽度优先搜索实现资源聚焦经典AI搜索问题——3×3滑动拼图的最短路径求解。资源以Java语言编写借助队列存储待扩展状态、哈希表去重完整呈现从状态表示、邻居生成到路径回溯的BFS核心流程适合用于算法课程实验、数据结构练习及面试准备。压缩包共19个文件约29KB包含3个java源码文件、3个class编译文件、4个xml与4个properties配置项以及jar包、manifest清单和说明文档覆盖源码、构建配置与可执行产物便于直接运行与二次修改。目前已有2037人学习下载读者可从中掌握BFS求解八数码的完整思路、状态去重技巧与Java工程组织方式并借助现成代码快速验证与调试自己的搜索算法实现。1. 八数码问题宽度优先搜索从状态空间到 Java 落地的完整拆解八数码问题8-Puzzle是很多算法课和笔试里绕不开的经典搜索题3×3 棋盘上放着 1 到 8 八个数字和一个空格每次只能把空格上下左右相邻的数字滑进来问从初始局面到目标局面最少要走多少步。它看起来简单但状态空间有 9!/2 181440 个可达状态手推几步就乱靠人脑枚举基本是玄学。宽度优先搜索BFS恰好是这类「每步代价相同、求最短路径」问题的标准解法而 Java 实现又能把队列、哈希去重、状态编码这些工程细节一次性讲透。这份资源就是围绕八数码的 BFS 求解展开的 Java 实现适合正在刷算法题、准备机试或者想搞懂「搜索算法怎么从伪代码变成能跑的程序」的开发者。下面我按自己拆项目的顺序把状态表示、判重、扩展、路径还原和性能边界一层层说清楚。2. 状态表示与判重BFS 能不能跑起来的关键八数码的 BFS 写不出来十有八九不是搜索逻辑错而是状态表示和判重没设计好。棋盘状态怎么存、怎么快速判断「这个局面我见过没有」直接决定程序是秒出结果还是跑到内存爆掉。2.1 用一维数组还是字符串表示状态最直观的表示是二维数组int[3][3]但它在入队、比较、哈希时都很别扭。常见做法是压成一维用长度为 9 的数组或字符串空格用 0 表示。比如目标状态1 2 3 4 5 6 7 8 0就存成123456780。// 用字符串表示状态空格记为 0 // 目标状态固定为 123456780 static final String TARGET 123456780; // 一维下标转二维坐标idx / 3 是行idx % 3 是列 static int rowOf(int idx) { return idx / 3; } static int colOf(int idx) { return idx % 3; }用字符串的好处是equals和hashCode都是现成的直接丢进HashSet就能判重不用自己写比较逻辑。代价是每次扩展状态都要做字符串拼接状态多的时候会有一定开销。如果追求性能可以改用int编码把 9 个数字按位压进一个整数判重时用boolean[]或位图速度会快不少。但对入门和大多数机试场景字符串版本足够清晰也够快。2.2 判重为什么必须做不做会怎样BFS 是按层扩展的如果不判重同一个局面会被从不同路径反复入队。八数码的状态图里有大量环比如空格左右横跳就能无限产生新节点队列会指数级膨胀程序要么卡死要么 OOM。所以判重不是优化是正确性的一部分。判重的核心数据结构是「已访问集合」。每从队列取出一个状态先看它是否在集合里扩展出的新状态如果没访问过才入队并标记。这里有个容易翻车的点标记时机。正确做法是入队时就标记而不是出队时才标记。否则同一层里多个父节点可能扩展出同一个子状态导致重复入队。QueueString queue new LinkedList(); SetString visited new HashSet(); queue.offer(start); visited.add(start); // 入队即标记别等到出队 while (!queue.isEmpty()) { String cur queue.poll(); if (cur.equals(TARGET)) { // 找到目标后续做路径还原 break; } for (String next : expand(cur)) { if (!visited.contains(next)) { visited.add(next); queue.offer(next); } } }expand负责把当前状态里空格上下左右能换的位置都换一遍生成合法的新状态。注意边界空格在第一行就不能再往上在最后一列就不能往右越界判断漏一个就会数组越界或者生成非法状态。2.3 状态扩展的边界处理扩展逻辑本身不复杂但边界条件是 bug 高发区。空格的位置决定了它能往哪几个方向走四个方向都要单独判断。static ListString expand(String state) { ListString result new ArrayList(); int zero state.indexOf(0); int r rowOf(zero), c colOf(zero); // 上下左右四个方向用偏移量表示 int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int[] d : dirs) { int nr r d[0], nc c d[1]; if (nr 0 || nr 2 || nc 0 || nc 2) continue; // 越界跳过 char[] arr state.toCharArray(); int nIdx nr * 3 nc; // 交换空格和目标位置 arr[zero] arr[nIdx]; arr[nIdx] 0; result.add(new String(arr)); } return result; }dirs数组把四个方向的坐标偏移写在一起比写四段 if 清爽。nr、nc是空格移动后的新坐标越界就continue。交换时先转char[]改完再转回字符串避免频繁创建中间对象。这段代码看着简单但zero的重新计算、nIdx的换算任何一个写错都会导致状态错乱建议写完先拿几个手工能推的局面验证。3. 路径还原与步数统计从「能不能解」到「怎么解」BFS 找到目标状态只完成了一半实际使用中我们往往还需要知道「最短步数是多少」以及「具体怎么走」。这就需要在搜索过程中记录父节点和移动方向最后回溯出完整路径。3.1 用父节点映射还原移动序列只统计步数的话可以在队列里存「状态 步数」的二元组或者按层计数。但要还原路径就得记录每个状态是从哪个状态、朝哪个方向走过来的。常见做法是用两个Map一个存父状态一个存移动方向。MapString, String parent new HashMap(); // 子状态 - 父状态 MapString, Character move new HashMap(); // 子状态 - 移动方向 // 扩展时记录来源 for (String next : expand(cur)) { if (!visited.contains(next)) { visited.add(next); parent.put(next, cur); move.put(next, dirChar); // U D L R queue.offer(next); } }dirChar根据方向偏移生成比如{-1,0}对应U。找到目标后从TARGET开始沿parent往回走把move里的方向收集起来再反转就是完整的移动序列。ListCharacter path new ArrayList(); String node TARGET; while (parent.containsKey(node)) { path.add(move.get(node)); node parent.get(node); } Collections.reverse(path); System.out.println(最短步数: path.size()); System.out.println(移动序列: path);这里有个细节parent里不包含起始状态所以循环条件用parent.containsKey(node)正好在回到起点时停止。反转后得到的序列是从起点到目标的顺序步数就是序列长度。3.2 步数统计的两种写法与取舍如果只关心最短步数不关心路径可以省掉parent和move改用按层扩展。每处理完一层步数加一。int steps 0; while (!queue.isEmpty()) { int size queue.size(); // 当前层的节点数 for (int i 0; i size; i) { String cur queue.poll(); if (cur.equals(TARGET)) { System.out.println(最短步数: steps); return; } for (String next : expand(cur)) { if (!visited.contains(next)) { visited.add(next); queue.offer(next); } } } steps; // 一层处理完步数加一 }size在循环开始前固定住保证只处理当前层的节点新入队的属于下一层。这种写法内存占用更小但拿不到具体路径。实际做题时如果题目只问步数就用这种问路径就用父节点映射别为了省事两种混着写容易把层数算错。3.3 无解情况的判断八数码不是所有初始局面都能到达目标。判断有无解用逆序数把状态按一维展开忽略空格数前面比后面大的数字对个数。逆序数为偶数则有解奇数则无解。BFS 本身也能「判断」——队列空了还没找到就是无解但那样要遍历完整个状态空间浪费时间。常见做法是入口先算一次逆序数无解直接返回。static boolean solvable(String state) { int inv 0; char[] arr state.replace(0, ).toCharArray(); for (int i 0; i arr.length; i) for (int j i 1; j arr.length; j) if (arr[i] arr[j]) inv; return inv % 2 0; }目标状态123456780的逆序数是 0偶数所以初始状态逆序数为偶数才有解。这个判断在 BFS 之前做一次能挡掉一批注定跑不出结果的输入。4. 避坑与排查八数码 BFS 最容易翻车的五个地方这段是我自己踩过、也看别人踩过的坑按「现象 → 原因 → 解决」整理照着排查基本能覆盖九成问题。4.1 程序跑很久不出结果现象小规模输入秒出稍微复杂一点的局面跑几分钟没反应内存持续上涨。原因判重没生效或者标记时机错了导致同一状态反复入队队列爆炸。解决检查visited.add是否在queue.offer之前执行确认expand生成的状态确实被visited.contains拦住了。可以在循环里打印队列大小正常应该稳定在几万以内如果一直涨就是判重漏了。4.2 结果步数比正确答案多现象能跑出结果但步数比标准答案大。原因按层计数时steps的位置放错或者把起始状态也算成了一步。解决确认steps初始为 0每处理完一整层再加一起始状态在steps0时检查如果起点就是目标答案应该是 0 而不是 1。4.3 数组越界或状态里出现重复数字现象抛ArrayIndexOutOfBoundsException或者生成的状态里数字重复、空格消失。原因expand里坐标换算写错交换时把两个位置搞混或者越界判断漏了某个方向。解决把rowOf、colOf和nIdx nr * 3 nc单独拿出来单元测试用几个已知坐标验证交换逻辑写成「先存临时变量再赋值」别用一行异或交换容易看花眼。4.4 无解输入把程序拖死现象某些输入永远跑不出结果也不报错。原因初始局面本身无解BFS 遍历完整个状态空间才停。解决入口先算逆序数奇数直接返回「无解」别让 BFS 白跑。这一步能省掉大量无效计算。4.5 字符串拼接导致性能差现象逻辑都对但状态一多就慢CPU 占用高。原因expand里频繁toCharArray和new String加上HashSet的哈希开销。解决状态量大时改用int编码 boolean[]判重或者用StringBuilder复用缓冲区。机试场景一般不用优化到这步但要知道瓶颈在哪。5. 进阶技巧双向 BFS 与状态编码优化单问 BFS 能解决八数码但状态空间大时它还是慢。真正让性能上一个台阶的是双向 BFS 和整数编码这两个技巧我在实际跑复杂局面时基本都会用上。5.1 双向 BFS 把搜索空间砍一半单向 BFS 从起点一层层往外扩最坏情况要摸到 18 万状态。双向 BFS 同时从起点和终点扩展两边在中间相遇就停。理论上搜索深度减半实际状态数能降一个数量级。// 双向 BFS 骨架两个队列、两个 visited QueueString q1 new LinkedList(), q2 new LinkedList(); SetString v1 new HashSet(), v2 new HashSet(); q1.offer(start); v1.add(start); q2.offer(TARGET); v2.add(TARGET); while (!q1.isEmpty() !q2.isEmpty()) { // 每轮选较小的队列扩展平衡两边 if (q1.size() q2.size()) { QueueString tq q1; q1 q2; q2 tq; SetString tv v1; v1 v2; v2 tv; } int size q1.size(); for (int i 0; i size; i) { String cur q1.poll(); for (String next : expand(cur)) { if (v2.contains(next)) { // 两边相遇合并步数即为最短 return; } if (!v1.contains(next)) { v1.add(next); q1.offer(next); } } } }关键点是每轮扩展前比较两个队列大小优先扩小的那边避免一边跑太远。相遇判断放在扩展新状态时只要新状态出现在另一边的visited里就说明找到了最短路径。步数统计要分别记录两边的层数相遇时相加。5.2 整数编码与位运算判重字符串状态在双向 BFS 里开销更明显因为要同时维护两个HashSet。把状态压成int能显著提速每个数字占 4 位9 个数字正好 36 位塞进long或int用int需要 4 位 × 9 36 位超出 32 位所以用long更稳。// 把 123456780 编码成 long每个数字占 4 位 static long encode(String s) { long code 0; for (int i 0; i 9; i) { code (code 4) | (s.charAt(i) - 0); } return code; }判重时用HashSetLong替代HashSetString哈希和比较都快得多。如果状态范围可控还能用boolean[]做位图但八数码的编码空间是 9! 级别位图太稀疏还是HashSet更实际。解码时按 4 位一组取出来还原成字符串或数组用于扩展。5.3 一个验证习惯我每次写完八数码 BFS都会固定跑三组用例一组起点即目标答案 0一组一步可达答案 1一组经典复杂局面比如123456780反过来打乱几步。三组都过基本能确认判重、扩展、步数统计三条链路没问题。从那以后我每次写搜索类代码都强制先跑「平凡用例 边界用例 复杂用例」这三板斧比事后 debug 省太多时间。希望帮到你。本文还有配套的精品资源点击获取