LeetCode 773. 滑动谜题

2025-03-13 HGNULB 约 7 分钟

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

分类

LeetCode CodeTop 困难未解决 2-5 字节猿辅导

题目描述

✅ 773. 滑动谜题

题意分析

棋盘固定为 2×3，包含数字 0 到 5，其中 0 表示空格。每一步只能把空格与上下左右相邻的数字交换，目标是按行排列成 123450。要求最少移动次数，已经完成时返回 0，无法到达目标时返回 -1。

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

核心思路

[!blue]

把整个棋盘视为图中的一个节点，一次合法交换就是一条边，所有边的代价都是 1。按行把六格编码成长度为 6 的字符串，既能唯一表示局面，也便于放入哈希集合判重。

字符串下标对应棋盘中的固定位置，预先用 neighbors 记录每格真正的上下左右邻居。找到当前 0 的下标后，分别与这些邻居交换，就枚举了所有且仅有的合法下一步。每次交换都从当前字符串复制字符数组，避免一种交换影响其他候选。

用 BFS 按层扩展：初始层只含起点，距离为 0；距离为 steps 的局面，其新邻居都能在 steps+1 步到达。只有当前层全部处理完才增加步数，因此第一次取出目标时，所有更短距离都已经检查过，当前步数就是最小值。

visited 记录完整局面，并在入队时标记。同一局面以后再出现时，路径不会更短，可以直接跳过。最多只有 6! 种排列，每种最多入队一次；队列耗尽后仍未找到目标，就说明所有可达局面都已检查，目标不可达。

解题步骤

按行编码起点，目标为 "123450"；起点就是目标时直接返回 0。

起点入队并加入 visited，初始化 steps = 0。

每轮先固定当前层的队列长度，只处理这些局面；遇到目标便返回 steps。

对每个局面找到空格，按邻接表生成交换后的状态，尚未访问的状态标记后入队。

当前层处理完令 steps++；队列为空仍未成功则返回 -1。

代码实现

class Solution {
    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 {
    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!\cdot6)$。最多处理 6! 个局面，每个局面至多生成 3 个邻居，定位空格、复制与哈希状态都只处理 6 个字符。固定棋盘尺寸下为常数规模。

空间复杂度：$O(6!\cdot6)$，队列和访问集合最多保存所有排列，每个状态长 6。

关键点总结

[!green]

访问标记针对完整局面，不能只记录空格位置。

拉直后的下标二与三跨行，不是真实相邻格。

易错点总结

[!yellow]

生成后继时污染原状态，会影响下一次交换。

每出队一个状态就增加步数，会把状态数量当距离。

没有按完整状态去重，会沿可逆移动反复展开。

相似题目

题目	难度	关联与区别
752. 打开转盘锁	中等	同样把完整局面当状态，用BFS寻找最少操作；邻居分别由移动空格或转动一位生成。
补充题 104. 矩阵行列循环移位的最少复原次数	困难	同样搜索矩阵状态，但变形题的一步是整行或整列循环移动，不能复用原题空格邻居规则。
127. 单词接龙	困难	把合法状态及一次操作建成无权图进行 BFS；本题按空位交换扩展棋盘状态，该题相差一个字符的单词之间连边。
1091. 二进制矩阵中的最短路径	中等	把合法状态及一次操作建成无权图进行 BFS；本题按空位交换扩展棋盘状态，该题按可通行的相邻单元扩展路径。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/43212310

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！