LeetCode 773滑动迷题：状态编码与BFS求解

LeetCode 773这道滑动迷题方法签名是public int slidingPuzzle(int[][] board)输入一个2x3的棋盘0代表空位每次可以把相邻数字滑进空位目标是还原成[[1,2,3],[4,5,0]]问最少移动次数无解返回-1。我第一次刷到它的时候是有点懵的迷宫BFS里节点坐标是现成的到了这题一个“状态”是整块棋盘连放visited里当key的东西都不知道该怎么设计。后来把它想透了才发现滑动迷题其实是“隐式图最短路”这类题目的绝佳入门题难点根本不在BFS本身而在状态编码和无解判断。1. 状态空间只有720个节点为什么这题还是Hard1.1 最少步数问题的标准套路看到“最少步数”第一反应应该是BFS而不是DFS。因为棋盘滑动的每一步代价都是1BFS第一次到达目标状态时的层数就是最短路径长度。这个结论对树、对迷宫、对隐式图统统成立关键点在于把题目转化成一张图。普通迷宫的状态是“二维坐标”。滑动迷题的状态是“整个盘面”一次移动会让盘面变化也就是说节点从“1个坐标pair”变成了“1个长度为6的排列”。很多人在这一步就开始挠头我该怎么表示这个节点怎么判断两个节点相同怎么生成邻居这也是为什么这题会被标Hard。它考的不是算法模板背得熟不熟而是能不能把一个具体问题抽象成图论模型并找到合适的状态压缩方式。1.2 为什么状态空间恰好只有720严格说是3602x3棋盘一共6个格子数字是0到5任意排列最多就是6! 720种。所以哪怕你完全不做优化用一个HashSet做visitedBFS最坏情况下也只会访问720个节点。这个规模小到什么程度大概就是几毫秒级别的事情。更准确地说从目标状态能到达的状态只有720的一半也就是360个。原因是滑动一次等价于把0和相邻数字做一次交换这会改变整个排列的奇偶性。空位从右下角出发最后要回到右下角在一个二分棋盘上走闭合回路步数一定是偶数所以整体置换一定是偶置换。因此可达状态被限制在全部排列的一半里面。这个理解很重要。面试官如果只满足于“BFS能AC”那这道题和普通题没什么区别但如果你能报出状态空间是360而不是720说明你真的理解搜索对象是谁。2. 状态编码是第一步别再拿int[][]当HashMap的Key2.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分别清空再重写。优点是HashMapInteger, Integer的哈希开销比字符串小Integer比较也比String的equals快缺点是代码可读性差面试时容易把自己绕晕。我刷题更推荐字符串工程里优化再考虑整数。2.3 邻居表把边界判断变成查表BFS扩展时核心操作是“找到0的位置尝试和相邻数字交换”。与其每次判断上下左右有没有越界不如预先把棋盘位置编号成0到5一次性列出每个位置的邻居位置坐标邻居位置0左上1, 31上中0, 2, 42右上1, 53左下0, 44下中1, 3, 55右下2, 4代码就是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} }; QueueString queue new ArrayDeque(); SetString 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允许nullArrayDeque不允许这题入队的字符串不可能是null用ArrayDeque更合适。严格来说在720个节点下性能差异完全看不出来但好习惯值得坚持。最后是char[]数组的生命周期。每次生成next时我都在循环体内部新建一个char[] arr拷贝当前字符串内容交换再new String(arr)。不要图省事把同一个char[]放在for循环外面复用那样一个分支改了数组另一个分支的字符串也可能会受影响。在这题里因为new String会复制内容复用问题不一定爆发但一旦你开始做带路径记录的变体这个坑就会跳出来咬人。3.3 复杂度分析可以说成“接近常数”每个状态最多3个邻居节点总数最多720边数最多也就是每个节点出度乘以节点数的一半大概在1000这个量级。BFS的时间复杂度是O(VE)空间复杂度也是O(V)。由于V是常量所以严格说这题的时间复杂度是O(1)面试官通常更希望听到的是“状态空间有限且只有360个可达状态所以可以在常数时间内完成搜索”。但要注意如果棋盘扩大到3x3甚至4x4这种朴素BFS会瞬间爆炸。3x3的8-puzzle状态数是9! 3628804x4的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(QueueString queue, MapString, Integer curDist, MapString, 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一下直接查表返回。MapString, Integer dist new HashMap(); QueueString 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 编码方式对比我把三种常见方案放在一起看方案可读性哈希开销代码量适用场景字符串HashSet高中短刷题、面试首选整数HashSet低低中状态规模较大性能敏感预计算全图dist中中中多次查询同一目标态我的结论很直接在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这类更大规模的滑动谜题你会自然地想到为什么需要启发式搜索也更容易理解“状态表示”和“搜索策略”到底是谁在影响性能。