LeetCode 909. 蛇梯棋

2026-03-28 HGNULB 约 6 分钟

文章信息 3 个分类 · 3 个标签

分类

LeetCode 中等 面试经典 150 题

标签

数组 广度优先搜索 矩阵

题目描述

✅ 909. 蛇梯棋

题意分析

棋盘编号从左下角的 1 开始，逐行交替向右、向左排列，终点是 n²。每次掷骰可以选择向前一到六格内的一个落点，但不能越过终点；如果落点有蛇或梯子，必须传送到指定编号。

一次掷骰最多传送一次，即使传送终点又是另一条蛇或梯子的起点，也不能在本轮继续跳转。求最少掷骰次数，无法到达终点时返回 -1；不是求期望次数，也不是每轮贪心选择能前进最远的落点。

解法：编号转换后的棋盘 BFS

核心思路

[!blue]

将一次掷骰及随后至多一次传送视为完整的一步操作。状态用这一步最终停下的编号表示：从状态 x 枚举骰子落点 y，再根据棋盘内容得到实际停留点 z，就相当于一条从 x 到 z、代价为一次掷骰的有向边。

所有边代价相同，因此用 BFS 逐层搜索。初始状态一号格位于零层；展开某层状态时产生的所有新状态，都能在多掷一次骰子后到达。第一次取出终点时，之前更少步数的状态已经搜索完，当前层数就是最短次数。

关键是将落点编号映射到矩阵坐标。先对 y - 1 除以 n、取余，得到从底部数起的行号和该行内的偏移。从底部数的偶数行向右编号，列号就是偏移；奇数行向左编号，列号改为 n - 1 - 偏移。最后用 n - 1 - 底部行号 转成矩阵从上到下的行下标。

根据这个坐标只读取一次蛇梯信息，得到 z 后按 z 标记访问。多个落点可能传送到同一个状态，后续决策只取决于最终位置；第一次到达已经使用最少骰子，再次到达不可能更好，可以直接跳过。蛇也可能让编号倒退，所以不能只根据编号大小限制搜索，访问标记同时防止环导致反复展开。

解题步骤

1. 将编号 1 入队并标记访问，初始掷骰次数为零。
2. 每层开始时固定队列当前长度，只展开这一层的状态。
3. 取出状态 x，若已经等于 n²，返回本层对应的掷骰次数。
4. 枚举 x + 1 到 min(x + 6, n²)，将编号转换成棋盘坐标。
5. 有蛇梯时传送一次，否则停在原落点；最终编号未访问时立即标记并入队。
6. 本层处理完后次数加一；队列耗尽仍未到达终点则返回 -1。

代码实现

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        Deque<Integer> q = new ArrayDeque<>();

        q.offer(1);
        int m = n * n;
        boolean[] vis = new boolean[m + 1];

        vis[1] = true;

        for (int answer = 0; !q.isEmpty(); ++answer) {
            for (int k = q.size(); k > 0; --k) {
                int x = q.poll();

                if (x == m) {
                    return answer;
                }

                for (int y = x + 1; y <= Math.min(x + 6, m); ++y) {
                    int i = (y - 1) / n;
                    int j = (y - 1) % n;

                    if (i % 2 == 1) {
                        j = n - j - 1;
                    }

                    i = n - i - 1;
                    int z = board[i][j] == -1 ? y : board[i][j];

                    if (!vis[z]) {
                        vis[z] = true;
                        q.offer(z);
                    }
                }
            }
        }

        return -1;
    }
}

func snakesAndLadders(board [][]int) int {
    n := len(board)
    q := []int{
        1,
    }
    m := n * n
    vis := make([]bool, m+1)
    vis[1] = true

    for answer := 0; len(q) > 0; answer++ {
        for k := len(q); k > 0; k-- {
            x := q[0]
            q = q[1:]
            if x == m {
                return answer
            }
            for y := x + 1; y <= min(x+6, m); y++ {
                i, j := (y-1)/n, (y-1)%n
                if i%2 == 1 {
                    j = n - j - 1
                }
                i = n - i - 1
                z := y
                if board[i][j] != -1 {
                    z = board[i][j]
                }
                if !vis[z] {
                    vis[z] = true
                    q = append(q, z)
                }
            }
        }
    }
    return -1
}

复杂度分析

• 时间复杂度：$O(n^2)$，共 n² 个编号，每个编号最多展开一次，每次至多枚举六个骰子落点。
• 空间复杂度：$O(n^2)$，用于访问标记和 BFS 队列。

关键点总结

[!green]

• 一条 BFS 边对应完整回合，传送不额外计数，也不允许连锁执行。
• 蛇形列方向由从底部开始的行号决定，再转换成矩阵实际行下标。
• 访问状态是传送后的最终位置，第一次到达即能保留最少次数。
• 固定本层长度，让下一次掷骰产生的状态留到下一轮处理。

易错点总结

[!yellow]

• 按矩阵从顶部开始的行号判断左右方向，棋盘尺寸变化时会映射错列。
• 编号没有先减一再除以行宽，会让每一行边界发生错位。
• 只标记骰子落点而不标记最终停留位置，会重复展开同一个传送终点。
• 把蛇梯算成额外一步，或到达新蛇梯后继续传送，都会改变一回合的题意。
• 每次只选择最大的编号，忽略后面蛇梯带来的路线差异，不能保证最少掷骰次数。

相似题目

题目	难度	关联与区别
752. 打开转盘锁	中等	同样把完整的一次操作作为图的一条边，BFS 层数给出最少操作数。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/89174011

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