LeetCode 773这道滑动迷题，方法签名是public int slidingPuzzle(int[][] board)，输入一个2x3的棋盘，0代表空位，每次可以把相邻数字滑进空位，目标是还原成[[1,2,3],[4,5,0]]，问最少移动次数，无解返回-1。我第一次刷到它的时候是有点懵的，迷宫BFS里节点坐标是现成的，到了这题一个“状态”是整块棋盘，连放visited里当key的东西都不知道该怎么设计。后来把它想透了才发现，滑动迷题其实是“隐式图最短路”这类题目的绝佳入门题，难点根本不在BFS本身，而在状态编码和无解判断。

1. 状态空间只有720个节点，为什么这题还是Hard

1.1 最少步数问题的标准套路

看到“最少步数”，第一反应应该是BFS而不是DFS。因为棋盘滑动的每一步代价都是1，BFS第一次到达目标状态时的层数就是最短路径长度。这个结论对树、对迷宫、对隐式图统统成立，关键点在于把题目转化成一张图。

普通迷宫的状态是“二维坐标”。滑动迷题的状态是“整个盘面”，一次移动会让盘面变化，也就是说节点从“1个坐标pair”变成了“1个长度为6的排列”。很多人在这一步就开始挠头：我该怎么表示这个节点？怎么判断两个节点相同？怎么生成邻居？

这也是为什么这题会被标Hard。它考的不是算法模板背得熟不熟，而是能不能把一个具体问题抽象成图论模型，并找到合适的状态压缩方式。

1.2 为什么状态空间恰好只有720（严格说是360）

2x3棋盘一共6个格子，数字是0到5，任意排列最多就是6! = 720种。所以哪怕你完全不做优化，用一个HashSet做visited，BFS最坏情况下也只会访问720个节点。这个规模小到什么程度？大概就是几毫秒级别的事情。

更准确地说，从目标状态能到达的状态只有720的一半，也就是360个。原因是滑动一次等价于把0和相邻数字做一次交换，这会改变整个排列的奇偶性。空位从右下角出发，最后要回到右下角，在一个二分棋盘上走闭合回路，步数一定是偶数，所以整体置换一定是偶置换。因此可达状态被限制在全部排列的一半里面。

这个理解很重要。面试官如果只满足于“BFS能AC”，那这道题和普通题没什么区别；但如果你能报出状态空间是360而不是720，说明你真的理解搜索对象是谁。

2. 状态编码是第一步：别再拿int[][]当HashMap的Key

2.1 字符串编码：便宜、直观、不易错

Java里int[][]不能直接做HashMap的key，因为数组的equals和hashCode都是引用比较，哪怕两个数组内容完全一样，只要不是同一个对象，HashMap就认为它们不同。你要是直接把board压进队列，BFS会永远扩张下去。

所以第一步是把二维盘面转成字符串。我的做法是按行优先展开：

private String encode(int[][] board) { char[] arr = new char[6]; for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { arr[i * 3 + j] = (char) (board[i][j] + '0'); } } return new String(arr); }

目标状态固定是"123450"，比如棋盘为[[1,2,3],[4,0,5]]就编码成"123405"，非常直观。调试的时候print出来就能看出当前盘面长什么样，这比二进制编码舒服多了。

有人会问：用Arrays.deepToString(board)直接生成带括号逗号的字符串不也能当key吗？理论上可以，但字符串会变成"[1, 2, 3], [4, 0, 5]"这种长格式，哈希和比较开销都比紧凑编码大，也没必要依赖默认toString行为。老老实实写一个encode函数，一劳永逸。

2.2 整数编码：省内存但要会位运算

当题目状态规模变大，字符串可能成为瓶颈，这时候可以考虑整数编码。6个数字，每个数字范围0到5，最多占3位二进制，但为了对齐方便一般用4位，总共24位，int完全放得下。

private int encodeToInt(int[][] board) { int state = 0; for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { state = (state << 4) | board[i][j]; } } return state; }

目标态编码结果就是0x123450。解码第pos个位置的数字时，用：

int digit = (state >> (4 * (5 - pos))) & 0xF;

每次交换0和邻居数字时，要把两个位置的4位bit分别清空再重写。优点是HashMap<Integer, Integer>的哈希开销比字符串小，Integer比较也比String的equals快；缺点是代码可读性差，面试时容易把自己绕晕。我刷题更推荐字符串，工程里优化再考虑整数。

2.3 邻居表：把边界判断变成查表

BFS扩展时，核心操作是“找到0的位置，尝试和相邻数字交换”。与其每次判断上下左右有没有越界，不如预先把棋盘位置编号成0到5，一次性列出每个位置的邻居：

代码就是：

int[][] neighbors = { {1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4} };

这样做的好处是不用每次判断坐标边界，也减少了因为行列坐标搞混而出错的概率。换成一个更大的棋盘，同样可以用程序预生成邻居表，这是一个很常用的预处理思路。

3. 经典BFS题解：完整代码和几个容易翻车的细节

3.1 完整代码

用字符串编码加BFS，完整实现大概是这样的：

public int slidingPuzzle(int[][] board) { String start = encode(board); String target = "123450"; if (start.equals(target)) { return 0; } int[][] neighbors = { {1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4} }; Queue<String> queue = new ArrayDeque<>(); Set<String> visited = new HashSet<>(); queue.offer(start); visited.add(start); int step = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { String cur = queue.poll(); int zeroIdx = cur.indexOf('0'); for (int nextIdx : neighbors[zeroIdx]) { char[] arr = cur.toCharArray(); arr[zeroIdx] = arr[nextIdx]; arr[nextIdx] = '0'; String next = new String(arr); if (next.equals(target)) { return step + 1; } if (visited.add(next)) { queue.offer(next); } } } step++; } return -1; } private String encode(int[][] board) { char[] arr = new char[6]; for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { arr[i * 3 + j] = (char) (board[i][j] + '0'); } } return new String(arr); }

这段代码可以直接跑通LeetCode 773，核心逻辑只有几行。

3.2 代码里的小心思

先说分层处理。我用int size = queue.size()和step++来记录层数，而不是在队列里存一个Node对象。优点是省内存，缺点是代码读起来需要一点BFS经验。如果你刚开始刷题，可以在队列里放一个数组[状态字符串, 步数]，但那种写法的内存开销在这题上也无所谓。

再说visited.add的返回值。HashSet的add方法在元素不存在时返回true，存在时返回false，所以“if (visited.add(next))”一行同时完成去重和入队判断，不需要先contains再add。很多老手写BFS都会这么用，既精简又不容易漏。

然后是ArrayDeque和LinkedList的选择。LinkedList也能当队列，但性能不如ArrayDeque，而且LinkedList允许null，ArrayDeque不允许，这题入队的字符串不可能是null，用ArrayDeque更合适。严格来说在720个节点下性能差异完全看不出来，但好习惯值得坚持。

最后是char[]数组的生命周期。每次生成next时，我都在循环体内部新建一个char[] arr，拷贝当前字符串内容，交换，再new String(arr)。不要图省事把同一个char[]放在for循环外面复用，那样一个分支改了数组，另一个分支的字符串也可能会受影响。在这题里因为new String会复制内容，复用问题不一定爆发，但一旦你开始做带路径记录的变体，这个坑就会跳出来咬人。

3.3 复杂度分析可以说成“接近常数”

每个状态最多3个邻居，节点总数最多720，边数最多也就是每个节点出度乘以节点数的一半，大概在1000这个量级。BFS的时间复杂度是O(V+E)，空间复杂度也是O(V)。由于V是常量，所以严格说这题的时间复杂度是O(1)，面试官通常更希望听到的是“状态空间有限，且只有360个可达状态，所以可以在常数时间内完成搜索”。

但要注意，如果棋盘扩大到3x3甚至4x4，这种朴素BFS会瞬间爆炸。3x3的8-puzzle状态数是9! = 362880，4x4的15-puzzle状态数是16!，那是天文数字。这也是为什么后续会出现A*、IDA*这些启发式搜索。

4. 无解判断：逆序数在2x3棋盘上的正确用法

4.1 逆序数定理怎么来

很多人在LeetCode的评论区看到过“这题可以用逆序数判断无解”的说法，但未必知道原理。简单说，滑动谜题的每个移动都是“0与相邻数字交换”，也就是一次对换。对换会改变排列的奇偶性，所以从目标态出发，所有可达状态的整体排列必须是偶置换。

对于2x3棋盘，列数为3，是奇数。这种情况下可解性的判断可以简化为：把棋盘去掉0之后的数字按行优先展开成一维序列，如果该序列的逆序对数为偶数，则可达；逆序对数为奇数，则不可达。

这里注意，列数为奇数和偶数的判断规则不一样，后面会细说。

4.2 一个极短的无解判断

求5个元素的逆序对数量，暴力两层循环就够了：

private boolean isSolvable(int[][] board) { int[] seq = new int[5]; int idx = 0; for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { if (board[i][j] != 0) { seq[idx++] = board[i][j]; } } } int inv = 0; for (int i = 0; i < 5; i++) { for (int j = i + 1; j < 5; j++) { if (seq[i] > seq[j]) { inv++; } } } return (inv % 2) == 0; }

验证几个例子。目标态去掉0是[1,2,3,4,5]，逆序数0，可解。LeetCode官方示例[[4,1,2],[5,3,0]]去掉0是[4,1,2,5,3]，逆序对为(4,1),(4,2),(4,3),(5,3)，一共4个，是偶数，确实有解，正确答案是5步。

再比如[[1,2,3],[5,4,0]]去掉0是[1,2,3,5,4]，逆序数为1，直接可以返回-1，连BFS都不用跑。

4.3 什么时候不能照搬这条规则

这个判断只对“标准目标态、列数为奇数”的棋盘成立。如果你面对的是4x4的15-puzzle，列数是偶数，判断条件还要额外考虑空位所在行。经典的可解性条件是：去掉0后的逆序数奇偶性与空位所在行到棋盘底部的行数奇偶性，两个要一致才可解。

另外，如果目标态不是“1,2,3,...,0”这种标准顺序，比如问你“能不能从某个状态拼成另一个指定状态”，那也需要重新推导，不能直接套用上面的代码。面试时可以主动提一句：“这里我用的是2x3的简化条件，如果棋盘列数为偶数，需要额外看0的位置。”这句话比代码本身更容易让面试官记住你。

5. 实测两类优化：双向BFS和整数编码值不值得写

5.1 双向BFS：原理不难，收益看场景

双向BFS的思路是同时从起点和目标态扩展，每次选节点数少的那一端扩展一层，当某一端遇到另一端已经访问过的状态时，两端的距离加起来就是答案。

核心代码骨架如下：

private int extend(Queue<String> queue, Map<String, Integer> curDist, Map<String, Integer> otherDist, int[][] neighbors) { int size = queue.size(); for (int i = 0; i < size; i++) { String s = queue.poll(); int step = curDist.get(s); int p = s.indexOf('0'); for (int nb : neighbors[p]) { char[] arr = s.toCharArray(); arr[p] = arr[nb]; arr[nb] = '0'; String next = new String(arr); if (otherDist.containsKey(next)) { return step + 1 + otherDist.get(next); } if (!curDist.containsKey(next)) { curDist.put(next, step + 1); queue.offer(next); } } } return -1; }

主循环里每次判断两端队列大小，扩展较小的一端。因为2x3棋盘状态空间只有360个可达状态，双向BFS的实际收益有限，更多是展示你理解“搜索深度减半能指数级减少节点”。我自己在本地测试的感觉是：单样例上从标准BFS的近乎全图扫描，变成两端各自扫一部分，差不多能省一半节点，但绝对值太小，时间上几乎没有体感差别。如果面试问优化，说双向BFS思路比实际写出来更重要。

5.2 更极端的做法：预计算全图距离

因为状态总数实在太少，还有一个更“暴力”的思路：从目标态"123450"做一次BFS，把所有可达状态到目标的步数存进一个HashMap。之后每个board只需要encode一下，直接查表返回。

Map<String, Integer> dist = new HashMap<>(); Queue<String> q = new ArrayDeque<>(); q.offer("123450"); dist.put("123450", 0); while (!q.isEmpty()) { String s = q.poll(); int p = s.indexOf('0'); for (int nb : neighbors[p]) { char[] arr = s.toCharArray(); arr[p] = arr[nb]; arr[nb] = '0'; String next = new String(arr); if (!dist.containsKey(next)) { dist.put(next, dist.get(s) + 1); q.offer(next); } } }

这个做法本质上是在以空间换时间。LeetCode单次调用看不出优势，但如果是一个后端服务需要快速回答成千上万个盘面的最短步数，预计算一次就能让后续每次查询变成O(1)。刷题时知道这个思路，遇到“同一个图多次查询最短路径”的变体就不慌。

5.3 编码方式对比

我把三种常见方案放在一起看：

我的结论很直接：在LeetCode 773这个题上，字符串编码+普通BFS已经是最优解。整数编码属于给自己找麻烦，双向BFS属于“会讲但没必要写”，预计算则适合当作面试结尾的加分扩展。

6. 滑动迷题背后的解题通法，以及面试怎么讲

6.1 这类题都可以拆成三步

“隐式图最短路”类题目，本质上都是同一个流程：定义状态编码、定义邻居生成规则、跑BFS。

拿几道题举例。LeetCode 752打开转盘锁，状态是4位字符串，每次把一位加一或减一，BFS求到target的最短步数；LeetCode 127单词接龙，状态是单词本身，邻居是只差一个字符的单词；LeetCode 847访问所有节点最短路径，状态是“当前节点+已访问集合”，用bit mask编码，是状态压缩BFS的进阶玩法。

把这些题放一起看就会发现，状态编码是区分它们难度的核心。滑动迷题是2x3、720个状态，所以字符串编码绰绰有余；一旦状态规模变大，就需要bit mask、双向BFS甚至A*。先学会在小状态空间里把编码做对，再去碰大状态空间的优化，是稳扎稳打的路子。

6.2 面试回答的顺序建议

如果面试考到这题，我的回答顺序会是：先把棋盘编码成字符串，说出目标态是"123450"；然后算一遍状态空间，说明最多360个可达状态，所以BFS在性能上没有压力；再给BFS实现，再补一句“无解情况可以用逆序数先判断”。

这个顺序让面试官能跟着你的思路走：你清楚搜的是什么图、图有多大、用什么数据结构表示节点、为什么BFS能找到最短步数。不要一上来就贴代码，更不要一开始就提A*，在这种小棋盘上用A*反而显得没想清楚问题规模。

6.3 我个人的建议

如果让我重新做一遍这道题，我会把80%的精力放在encode函数的设计上，而不是BFS本身。把“一个盘面如何变成一个字符串”想清楚，代码几乎就是标准模板；想不清楚，写再多循环都是白搭。

另外建议做完之后，自己把队列里弹出的每个状态都打印出来，观察一下BFS的扩展顺序，亲手验证从"123450"推出来的360个状态长什么样。这样你才会对“状态空间”四个字有身体记忆，而不是只停留在理解层面。见过这些状态之后，再去看8-puzzle、15-puzzle这类更大规模的滑动谜题，你会自然地想到为什么需要启发式搜索，也更容易理解“状态表示”和“搜索策略”到底是谁在影响性能。