LeetCode 773. 滑动谜题

2025-03-13 HGNULB 约 15 分钟

文章信息 7 个分类 9 个标签

分类

题目描述

✅ 773. 滑动谜题

题意分析

一块 2 行 3 列的板子上摆着数字 1 到 5 和一个用 0 表示的空格。每一步可以把 0 与它上下左右相邻的某个数字互换位置。问最少需要多少步才能把板子变成 [[1,2,3],[4,5,0]]；无论怎么走都到不了就返回 -1。

要什么：最少步数。这三个字是整道题的路标——每一步的代价都是 1，没有权重差异，这就是无权图上的单源最短路，标准答案是 BFS。用 DFS 或回溯去搜也能找到解，但找到的不保证是最短的，还得把所有路径都搜完再取最小，指数级爆炸。

把问题翻译成图：图的节点不是格子，而是整块板子的一个摆放状态；两个状态之间有边，当且仅当能通过一次合法移动互相转换。起点是给定的初始状态，终点是 [[1,2,3],[4,5,0]]，问的是两点间的边数。这个「节点 = 整个局面」的建模视角是这类谜题题的通用套路，也是初学者最容易卡住的一步。

约束透露的信号极其关键：棋盘固定是 2×3，不是变长的。六个格子上放着六个互不相同的值，所以状态总数最多 $6! = 720$ 个。七百多个节点的图，BFS 想怎么跑就怎么跑，完全不用担心状态爆炸——这也是为什么本题虽标为困难，实际难度主要在建模而非优化。固定尺寸还带来两个便利：状态可以压成一个长度 6 的字符串，相邻关系可以直接写死成一张邻接表。

另一个必须注意的点是答案可能是 -1。滑动谜题的所有可达状态构成置换群的一个子群，$6!$ 个排列会被分成两个互不相通的等价类（对应排列的奇偶性），初始状态若与目标不在同一类里就永远拼不出来。代码上不需要显式判断奇偶——BFS 把能到的都走完仍未命中，自然返回 -1。

边界：初始状态可能就是目标，答案为 0；board 中的值保证是 0 到 5 的一个排列，不必校验；0 在四个角落时只有 2 个相邻格，在中间时有 3 个，邻接表的长度不一致。

解法：字符串状态压缩 + BFS

核心思路

先看为什么不能沿用「在网格上做 BFS」的直觉。网格 BFS 的节点是坐标，访问标记是一个二维布尔数组；但这道题里同一个坐标可以在不同的局面下被反复经过，坐标根本不足以刻画「走到哪儿了」。真正在变化的是整块板子的排列。所以第一步必须完成视角切换：节点 = 局面，边 = 一次合法移动。

完成切换之后，剩下的问题是「局面怎么表示才便于当哈希键」。二维数组不能直接进 HashSet（Java 里数组比较的是引用），逐次深拷贝也很啰嗦。注意到棋盘固定 2×3，把两行首尾相接拉直成长度 6 的序列，用一个字符串表示即可：[[1,2,3],[4,5,0]] 就是 "123450"。字符串天生可哈希、可比较、不可变，正好当作状态的身份证。这一步叫状态压缩——把一个结构化的局面编码成一个标量。

拉直之后还要解决「谁和谁相邻」。原本是二维的上下左右，拉直后变成一维下标之间的映射关系。因为尺寸固定，直接把这张表写死最省事：
下标布局：0 1 2
          3 4 5
下标 0 的邻居是 1（右）和 3（下）；下标 1 的邻居是 0、2、4；下标 2 是 1、5；下标 3 是 0、4；下标 4 是 1、3、5；下标 5 是 2、4。写成 neighbors = {{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}}。预先写死邻接表，比每次现算 row = i / 3, col = i % 3 再判四个方向是否越界要可靠得多——后者最容易犯的错是没意识到「下标 2 和下标 3 在一维上相邻，但在二维上分属不同行的两端，不能互换」。

转移规则也随之简化：一个局面的所有后继，就是把 0 与它在邻接表里的每个邻居互换后得到的新字符串。0 的位置一查就有，不需要遍历整块板。

最后是 BFS 本身。用分层写法：每轮循环开始时记下队列当前长度 size，把这一整层出完队再把 steps 加一。不变量是：每一层出队的所有状态，到起点的最短距离恰好等于当前的 steps。这条不变量成立的前提是无权图上 BFS 的基本性质——先入队的状态距离不会更大。

访问标记必须在入队时打，而不是出队时。否则同一个状态可能在被处理之前从多条路径重复入队，队列膨胀，极端情况下退化成指数级。代码里用 visited.add(nextState) 的返回值同时完成「判重」和「标记」两件事，是一个既短又不会写漏的惯用法。

解题步骤

把 board 按行优先拉直成长度 6 的字符串 start，目标固定为 "123450"。为什么用字符串：它可哈希、不可变、比较成本低，直接就能当 HashSet 的键与队列元素；用 int[] 则每次都要手动深拷贝且无法直接判重。

若 start 已等于目标则直接返回 0。为什么：虽然主循环第一轮出队时也会命中并返回 steps = 0，但这个前置判断让「零步」这个边界一眼可见，是可读性上的选择。

写死邻接表 neighbors。为什么不现算方向：拉直后的一维下标之间，只有同行左右与同列上下才算相邻；现算时若忘记判断「跨行」，会把下标 2 与 3 误认为相邻，产生一次物理上不可能的移动，从而算出偏小的步数。写死六行数据是 $O(1)$ 的心智成本换来零出错率。

起点入队，同时加入 visited。为什么标记要与入队同时发生：BFS 的正确性只要求每个状态被处理一次；若等到出队才标记，同一状态会从多个前驱重复入队，队列规模失控。

外层 while 每轮先记下 size = queue.size()，内层循环恰好处理这么多个。为什么必须先取快照：内层会往队列里追加下一层的状态，若直接用 queue.size() 当循环条件，层与层的边界就消失了，steps 也就不再等于最短距离。

出队后先判断是否等于目标，命中就返回当前的 steps。为什么在出队时判而不是入队时判：两种写法都对，但出队时判的写法让「steps 的含义 = 当前层的距离」保持统一，不需要在入队分支里额外加一；代价是目标状态会多在队列里待一轮，对 720 个状态而言可以忽略。

用 cur.indexOf('0') 定位空格，对邻接表中的每个下标做一次交换，生成新状态。为什么只需要看 0：一次合法移动必然涉及 0，除 0 之外的任何两个数字都不能直接互换。

新状态用 visited.add(...) 判重，返回 true（即之前没见过）才入队。为什么用返回值：HashSet.add 在元素已存在时返回 false，一次调用同时完成查询与插入，比先 contains 再 add 少一次哈希计算，也杜绝了两处条件写得不一致的可能。

一层处理完 steps++；队列耗尽仍未命中则返回 -1。为什么可以断定无解：BFS 会遍历从起点可达的全部状态，队列空意味着可达集合已穷尽，目标不在其中。

以 具体用例 board = [[1,2,3],[4,0,5]] 走一遍，预期答案是 1。

编码：拉直得到 start = "123405"，目标 "123450"。两者不等，进入 BFS。
初始化：queue = ["123405"]，visited = {"123405"}，steps = 0。

第一层（size = 1，此层所有状态到起点距离为 0）：
出队 "123405"，不等于目标。定位 0 的下标：字符串是 1 2 3 4 0 5，0 在下标 4。查 neighbors[4] = {1, 3, 5}。
与下标 1 交换："103425"，未访问过，标记并入队。这一步在二维上是把 0 往上挪。
与下标 3 交换："123045"，未访问过，标记并入队。这一步是 0 往左挪。
与下标 5 交换："123450"，未访问过，标记并入队。这一步是 0 往右挪，正好得到目标。
本层结束，steps 变成 1。队列现在是 ["103425", "123045", "123450"]。

第二层（size = 3，此层所有状态到起点距离为 1）：
出队 "103425"，不等于目标，继续扩展它的三个后继。
出队 "123045"，不等于目标，同样扩展。
出队 "123450"，等于目标，返回当前的 steps = 1。

答案 1，与预期一致。注意目标是在第二层出队时被命中的，而 steps 此时已经是 1——这正是「先把整层出完再 steps++」所保证的：第 $d$ 层出队的状态，距离恰好是 $d$。

再看一个无解用例 board = [[3,2,4],[1,5,0]]：BFS 会把与它同奇偶类的全部 360 个状态都访问一遍，始终碰不到 "123450"，队列耗尽后返回 -1。代码不需要任何奇偶性判断，穷尽可达集合这件事本身就给出了答案。

代码实现

class Solution {
    // 棋盘固定 2x3，可把状态压成长度 6 的字符串，状态数有限，BFS 不会爆炸。
    public int slidingPuzzle(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int[] row : board) {
            for (int v : row) {
                sb.append(v);
            }
        }

        String start = sb.toString();
        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 steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(target)) {
                    return steps;
                }

                int zero = cur.indexOf('0');
                for (int next : neighbors[zero]) {
                    String nextState = swap(cur, zero, next);
                    if (visited.add(nextState)) {
                        queue.offer(nextState);
                    }
                }
            }
            steps++;
        }

        return -1;
    }

    private String swap(String s, int i, int j) {
        char[] chars = s.toCharArray();
        char first = chars[i];
        chars[i] = chars[j];
        chars[j] = first;
        return new String(chars);
    }
}

func slidingPuzzle(board [][]int) int {
    // 棋盘固定 2x3，可把状态压成长度 6 的字符串，状态数有限，BFS 不会爆炸。
    start := make([]byte, 0, 6)
    for _, row := range board {
        for _, v := range row {
            start = append(start, byte('0'+v))
        }
    }
    s := string(start)
    target := "123450"
    if s == target {
        return 0
    }

    neighbors := [][]int{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}
    queue := []string{s}
    visited := map[string]bool{s: true}

    steps := 0
    head := 0
    for head < len(queue) {
        size := len(queue) - head
        for i := 0; i < size; i++ {
            cur := queue[head]
            head++

            if cur == target {
                return steps
            }

            zero := findZero(cur)
            for _, next := range neighbors[zero] {
                ns := swap(cur, zero, next)
                if !visited[ns] {
                    visited[ns] = true
                    queue = append(queue, ns)
                }
            }
        }
        steps++
    }

    return -1
}

func findZero(s string) int {
    for i := 0; i < len(s); i++ {
        if s[i] == '0' {
            return i
        }
    }
    return -1
}

func swap(s string, i int, j int) string {
    chars := []byte(s)
    chars[i], chars[j] = chars[j], chars[i]
    return string(chars)
}

复杂度分析

时间复杂度：$O(6! \times 6)$，即常数级。凭什么：状态空间的上界是六个互不相同的值在六个格子上的全排列，共 $720$ 个；每个状态至多出队一次，出队后要定位 0（扫 6 个字符）、生成至多 3 个后继（每个后继要复制一份长度 6 的字符串并做一次哈希）。所有因子都是与输入无关的常数，因此这道题严格来说是 $O(1)$ 的——棋盘尺寸固定是把复杂度钉死的根本原因。若推广到 $m \times n$，状态数变成 $(mn)!$，BFS 立刻不可行，那时需要 A* 配合曼哈顿距离启发函数。

空间复杂度：$O(6! \times 6)$，同样是常数级。凭什么：visited 最多装下 720 个长度 6 的字符串，队列的规模不会超过状态总数。相比之下，若用 int[][] 表示状态并逐层深拷贝，常数会大出一个量级且无法直接判重。

关键点总结

「最少步数」+「每步代价相同」= BFS。这是最短路建模的第一反射。看到「最少操作次数」「最短变换序列」而每次操作代价一致时，不要去想 DP 或贪心，先把它翻译成无权图。

节点未必是题面里显式给出的实体，往往是「整个局面」。滑动谜题、打开转盘锁、单词接龙都共享这个视角：状态空间里的一个点 = 系统的一个完整快照。能不能完成这层抽象，是这类题的真正分水岭。

状态压缩的目标是得到一个可哈希、可比较的标量。字符串是最省事的载体；若状态含义更规整（如每格取值范围小），也可以编码成整数用位运算处理，速度更快但可读性差。选哪种取决于是否卡常。

固定尺寸的相邻关系直接写死邻接表。把二维的方向数组换算成一维下标是高频错误源，尤其是「行末与下一行行首在一维上挨着但物理上不相邻」这个坑。六行常量数据的可靠性远高于现场推导。

访问标记必须在入队时打，不能等到出队。这是 BFS 正确性与效率的共同前提；用 Set.add 的布尔返回值一次搞定判重与标记，是值得固化的写法。

分层 BFS 要先给队列长度拍快照，否则内层追加的新状态会混进本层，层数与距离的对应关系被破坏。

无解不需要额外判定，队列耗尽即为无解。BFS 天然穷尽可达集合，这一点让「滑动谜题的奇偶不变量」这类数学结论成为可选的加分项而非必需品。

面试视角：这题被问到时，先花半分钟说清「节点是局面、边是一次移动、要求无权最短路」，再说「棋盘固定 2×3 所以状态数最多 720，BFS 完全够用」，最后才动手。写完后主动补两句能明显加分：一是「访问标记要在入队时打」，二是「如果棋盘尺寸放大，$（mn）!$ 会爆炸，需要改用 A* 并以每个数字到目标位置的曼哈顿距离之和作为启发函数，也可以用双向 BFS 把搜索层数减半」。此外，能顺口提一句「滑动谜题有一半的初始状态无解，因为一次移动改变排列的奇偶性」，说明你不只是在套模板。

易错点总结

错误写法：不做状态压缩，直接把 int[][] 放进 HashSet → 用例任意，Java 中数组的 hashCode 基于引用而非内容，两个内容相同的数组会被当成不同元素，visited 完全失效，BFS 陷入无限扩展直到内存耗尽。

错误写法：现算相邻关系时写成「下标 i 与 i-1、i+1 相邻」 → 用例 board = [[1,2,3],[4,5,0]] 之外的任意局面，下标 2（第一行末尾）与下标 3（第二行开头）会被误判为相邻，产生一次物理上不存在的移动，算出的步数偏小甚至把无解局面判成有解。

错误写法：把访问标记放在出队时（visited.add(cur) 写在 poll 之后） → 用例是任意需要多步的局面，同一个状态会从多个前驱重复入队，队列规模指数级膨胀；720 个状态的题目虽然不至于超时，但这个习惯搬到大状态空间的题上会直接爆内存。

错误写法：外层循环写成 for (int i = 0; i < queue.size(); i++)（不取快照） → 用例 board = [[1,2,3],[4,0,5]]，内层入队的三个新状态让 queue.size() 在循环中不断变大，本层与下一层混在一起，steps 不再等于最短距离，返回值偏小。

错误写法：用 DFS 或回溯搜索并记录最小步数 → 用例 board = [[4,1,2],[5,0,3]]（答案是 5），DFS 会沿着某条深路径一直走下去，不加剪枝时状态可重复访问导致不终止；即便加了访问集合，找到的第一个解也不保证最短，必须搜完全部路径，代价远高于 BFS。

错误写法：目标字符串写成 "012345" 或 "123456" → 用例任意，前者把空格误放在左上角，后者根本不是合法状态（没有数字 6），BFS 永远命中不了，恒返回 -1。目标是 [[1,2,3],[4,5,0]] 拉直后的 "123450"。

错误写法：交换时直接在原字符串的字符数组上改而不复制 → 用例任意，Java 中 String 不可变尚且安全，但若改用 char[] 表示状态并在同一个数组上反复交换，一个后继生成后会污染下一个后继的计算，扩展出的状态全是错的；每次交换都必须基于当前状态的一份独立副本。

错误写法：steps++ 放在内层循环里 → 用例 board = [[1,2,3],[4,0,5]]，第一层展开三个后继就把 steps 加了三次，返回值远大于真实的 1。步数是按层递增的，不是按节点递增。

错误写法：认为无解时应该抛异常或返回 0 → 用例 board = [[3,2,4],[1,5,0]]，正确答案是 -1；返回 0 会被误读成「已经是目标状态」。

错误写法：只把 0 往一个方向（比如只往右和往下）移动 → 用例 board = [[4,1,2],[5,0,3]]，需要 0 反复来回移动才能归位，限制方向会让目标不可达，错误返回 -1。移动是双向的，邻接表必须对称。

错误写法：Go 中用 queue = queue[1:] 出队，同时又用 len(queue) 算本层大小 → 切片头指针推进后 len 会随之缩短，与「本层还剩多少个」的语义对不上；要么像本文这样用 head 下标推进并用 len(queue) - head 算剩余量，要么每层单独用一个新切片。

相似题目

题目	难度	考察点
752. 打开转盘锁	中等	状态同为定长字符串，但转移是每位加一减一，还要处理死亡数字这层额外约束
127. 单词接龙	困难	状态是词表中的单词，邻接关系需要构造（按通配模式建桶），是本题的变长版
854. 相似度为 K 的字符串	困难	同为交换字符求最少步数，但字符串更长，必须靠「只交换能立刻归位的字符」剪枝
909. 蛇梯棋	中等	状态是棋盘编号，难点在蛇形编号与二维坐标的换算，转移是掷骰子的六个分支
1345. 跳跃游戏 IV	困难	状态是下标，但同值下标之间两两可达，必须在用完后清空该值的桶以避免重复展开
1293. 网格中的最短路径	困难	状态需要额外携带「还能消除几个障碍」这一维，是二维坐标加资源的三元组
1129. 颜色交替的最短路径	中等	状态携带「上一条边的颜色」，同一个节点在两种颜色下要分别记访问
994. 腐烂的橘子	中等	多源 BFS，起点是全部腐烂橘子，考的是初始化时把多个源一次性入队
542. 01 矩阵	中等	同为多源 BFS，但要求每个格子到最近 0 的距离，答案是一整张距离表而非单个值
1091. 二进制矩阵中的最短路径	中等	网格 BFS 的基础形态，节点就是坐标本身，八方向移动，无需状态压缩
1654. 到家的最少跳跃次数	中等	状态要带上「上一步是否向后跳」，且搜索上界需要自己论证，边界最难把握
LCR 109. 打开转盘锁	中等	与 752 同题，可直接套用