LeetCode 909. 蛇梯棋

2026-03-28 HGNULB 约 12 分钟

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

分类

题目描述

✅ 909. 蛇梯棋

题意分析

题目目标：$n \times n$ 的棋盘上按回环（Boustrophedon）方式从左下角开始编号 1 到 $n^2$。从方格 1 出发，每一步可以掷出 $1 \sim 6$ 中任意一个数并前进到 x+1 至 x+6 中的任一格；若落点格子上标着一个正数，则必须再传送到该编号的格子（蛇或梯子）。求到达 $n^2$ 所需的最少步数，不可达返回 -1。

核心约束：三条。第一，「最少步数」且每一步代价都是 1 → 无权图最短路，BFS。第二，编号是回环的：从下往上数第一行从左到右、第二行从右到左，交替进行，所以编号与二维下标之间的映射不是简单的除法取模，必须做两次翻转。第三，「传送只发生一次」——落到蛇尾或梯子底之后传送到目标格，即使目标格上也写着数字也不再继续传送，这条规则决定了状态图里每条边的终点只需算一次。

边界处理：x + 6 可能超过 $n^2$，要与 $n^2$ 取小；玩家可以选择不掷满 6，所以要枚举全部 6 个落点而不只是最远那个；起点 1 本身可能不带传送（题目保证格子 1 和 $n^2$ 上不会有蛇或梯子）；棋盘可能构成死路，此时返回 -1。

实现取舍：可以先把整个棋盘按编号展平成一维数组再 BFS（编号映射只做一次，逻辑清爽），也可以在 BFS 过程中即时换算（省一次 $O(n^2)$ 的预处理与一份数组）。本文用后者，把换算封装在最内层循环里。

解法：广度优先搜索

核心思路

先把题目翻译成图：顶点是方格编号 $1 \sim n^2$，从编号 $x$ 出发有至多 6 条边，分别指向 x+1 到 x+6（越界的丢弃）经过一次可能的传送之后的最终落点，求 1 到 $n^2$ 的最短路径边数。翻译完成后就是模板 BFS，剩下两个难点都是细节：编号怎么换算成坐标，以及传送怎么处理。

先解决编号映射。设编号 $y$（1 起），令 i = (y-1) / n、j = (y-1) % n，这是假设编号从左上角开始、逐行从左到右时的坐标。真实规则要在此基础上做两次修正。第一次是行内方向：编号从下往上每行交替方向，i 为奇数的那些行是从右往左的，所以要把列号镜像成 j = n - 1 - j。第二次是行序：编号从最下面一行开始，而数组下标 0 是最上面一行，所以最后把 i 翻转成 i = n - 1 - i。两次翻转的顺序不能颠倒——列的镜像依赖的是「翻转前」的行号奇偶性，若先翻行号再判奇偶，当 $n$ 为偶数时奇偶性会整体反相，映射全错。

再解决传送。读到 board[i][j] 后，若它是 -1 说明是普通格子，落点就是 y 本身；否则落点是 board[i][j] 这个编号。用一行 z = board[i][j] == -1 ? y : board[i][j] 表达，并且只做一次——不递归、不循环，因为规则明确说明传送不连锁。

于是不变量是：BFS 队列中同一层的所有编号，从方格 1 到它们的最少步数相同，等于当前的 answer。代码用「按层扩展」的写法：外层 for 的每一轮开始时先固化当前队列大小 k，恰好弹出 k 个作为一层，处理完后 ++answer。vis 数组按最终落点 z 标记，而不是按中间的 y 标记——因为图的顶点是「落点」，两个不同的 y 完全可能因为蛇梯而传送到同一个 z，只需要访问一次。

终点判定写在出队时。这样起点即终点的退化情形（$n = 1$）会在第 0 层直接命中并返回 0，不需要额外特判。

解题步骤

第一步：编号 1 入队并标记 vis[1]，m = n * n 作为终点编号。 为什么起点也要标记：否则某条路径可能通过蛇梯绕回 1，造成重复展开。

第二步：外层循环以 answer 为层号，内层先取 k = q.size() 再循环 k 次。 为什么先固化层大小：循环体内会往队列追加下一层的节点，直接用 q.size() 当条件会把新旧两层混在一起，answer 与真实步数脱钩。

第三步：出队编号 x，若 x == m 立即返回 answer。 为什么此时一定是最短：由不变量，出队元素所在层号就是它的最短步数，BFS 逐层推进，第一次遇到终点必然最短。

第四步：枚举 y 从 x + 1 到 min(x + 6, m)。 为什么要枚举全部 6 个而不是只走最远的：蛇可能把远处的格子拉回起点附近，贪心地每次跳 6 格并不最优；玩家有权选择掷出任意点数，这是「求最优」而非「模拟随机」。为什么与 m 取小：超过 $n^2$ 的落点不存在，题目也不允许越过终点。

第五步：把 y 换算成坐标。先 i = (y-1) / n、j = (y-1) % n，若 i 为奇数则 j = n - 1 - j，最后 i = n - 1 - i。 为什么这个顺序：列镜像的判据是「从下往上数的第几行」，也就是翻转前的 i；先翻行号会破坏这个判据。

第六步：z = board[i][j] == -1 ? y : board[i][j]，若 !vis[z] 则标记并入队。 为什么只传送一次：题目规定落到目标格后不再继续传送。为什么标记的是 z 不是 y：图的顶点是落点，多个 y 可能传送到同一个 z，按 y 标记会让同一个顶点被重复入队。为什么入队时就标记：出队时才标记会让同层的多个前驱把同一个 z 反复入队，队列规模失控。

第七步：队列耗尽仍未命中终点，返回 -1。

以 $n = 6$、board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] 走一遍（终点 m = 36）：

先验证几个关键的编号映射。编号 2：i = 1/6 = 0、j = 1 % 6 = 1，i 是偶数不镜像列，最后 i = 5，取 board[5][1] = 15——即方格 2 上有一架通往 15 的梯子。编号 17：i = 16/6 = 2、j = 16%6 = 4，i 偶数，i 翻转为 3，取 board[3][4] = 13——方格 17 上有一条通往 13 的蛇。编号 14：i = 13/6 = 2、j = 1，翻转后 i = 3，取 board[3][1] = 35——通往 35 的梯子。编号 7：i = 6/6 = 1 是奇数，j = 0 镜像成 5，i 翻转成 4，取 board[4][5] = -1，普通格。

第 0 层（answer = 0）：出队 1，不是 36。枚举落点 2~7：落点 2 触发梯子传送到 15，标记入队；落点 3、4、5、6、7 都是普通格，各自入队。队列变成 [15, 3, 4, 5, 6, 7]，answer 变为 1。

第 1 层：依次出队上述 6 个编号，都不是 36。其中出队 15 时枚举落点 16~~21，落点 17 触发蛇传送到 13，标记入队；其余落点均为普通格入队。出队 3~~7 时同样产生一批未访问的普通格。这一层结束，answer 变为 2，队列中包含 13。

第 2 层：出队时轮到 13，枚举落点 14~19，其中落点 14 触发梯子传送到 35，标记入队。这一层结束，answer 变为 3，队列中包含 35。

第 3 层：出队 35，枚举落点 36（min(35+6, 36) = 36），board 上对应位置是 -1，z = 36，未访问，入队。这一层结束，answer 变为 4。

第 4 层：出队 36，等于 m，返回 answer = 4。对照官方解释：1 → 2（梯子）→ 15 → 17（蛇）→ 13 → 14（梯子）→ 35 → 36，恰好四次掷骰，与期望一致。

代码实现

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, 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^2$ 个顶点；每次出队枚举至多 6 个落点，每个落点的坐标换算和传送查询都是常数时间，因此总量是 $6n^2$ 量级。

空间复杂度：$O(n^2)$。凭什么：vis 数组长度为 $n^2 + 1$，队列最坏情况下同时容纳 $O(n^2)$ 个编号；棋盘本身是输入，不计入额外空间。

关键点总结

等权最短路一律 BFS，不要上 Dijkstra。 每次掷骰的代价都是 1，堆只会带来额外的 $\log$ 开销。

回环编号的映射要「先按普通行优先算，再翻列、再翻行」，顺序不可交换。 列的镜像依据是翻转前的行奇偶性，这是本题最密集的出错点，写完必须用具体编号（比如 1、2、$n$、$n+1$、$n^2$）逐个验算。

必须枚举全部 6 个落点。 蛇会把远处的格子拉回来，「每次跳最远」的贪心是错的；这题的本质是求最优决策序列而非模拟游戏。

蛇梯传送只做一次，不连锁。 写成 while (board[...] != -1) 会在互指的蛇梯对上死循环。

访问标记按最终落点打，且在入队时打。 按中途编号标记会重复展开同一个顶点；出队才标记会让队列规模膨胀。

面试视角：先明确把题目翻译成图并说清顶点、边、代价，再单独用两分钟把编号映射推给面试官看（当场验算编号 1、2 和 $n^2$ 三个点），最后套 BFS 模板。面试官常见追问有两个：一是「为什么不能贪心每次跳 6 格」——用一个「第 6 格是长蛇」的反例回答；二是「如果骰子面数变成 $k$」——只需把内层枚举上界改成 x + k，复杂度变成 $O(kn^2)$。

易错点总结

错误写法：编号映射时先翻行号再判奇偶，写成 i = n - 1 - i; if (i % 2 == 1) j = n - 1 - j; → 用例 $n = 6$，编号 7 应落在 board[4][5]，错误写法算出 i = 5 为奇数从而镜像列得到 board[5][5]，整张棋盘的蛇梯位置全部错位。

错误写法：忘记行内镜像，直接用 i = (y-1)/n、j = (y-1)%n 加行翻转 → 用例 $n = 6$，编号 7 会落到 board[4][0] 而不是 board[4][5]，所有偶数行（从下往上数第二、四、六行）的格子全部读错。

错误写法：忘记行翻转，只做列镜像 → 用例 $n = 6$，编号 2 会落到 board[0][1] 而不是 board[5][1]，起点附近的梯子完全读不到，答案偏大或返回 -1。

错误写法：只把落点取最远的 x + 6 一个 → 用例中若 x + 6 恰好是一条把人拉回起点的长蛇，而 x + 1 是一条通往终点的梯子，贪心会绕远甚至死循环，返回值大于最优解。

错误写法：落点上限不与 m 取小 → 用例 $n = 6$、x = 35，会枚举到 41，换算坐标时 i = 40/6 = 6 越界抛异常。

错误写法：传送写成 while (board[i][j] != -1) { y = board[i][j]; 重新换算坐标 } → 用例中存在方格 A 指向 B、B 指向 A 的互指蛇梯时进入死循环；题目明确规定只传送一次。

错误写法：vis 标记打在中途编号 y 上而不是落点 z 上 → 用例 $n = 6$ 中方格 2 与方格 3 若都通往 15，两条路径都会把 15 入队，同一个顶点被重复展开，最坏情况下队列规模指数增长。

错误写法：出队时才标记 vis → 用例中同一层的多个编号都能到达同一个落点，该落点被重复入队多次，队列迅速膨胀导致超时。

错误写法：内层层循环写成 for (int k = 0; k < q.size(); ++k) → 用例任意棋盘，q.size() 随入队不断增大，当前层与下一层混在一起，answer 只增加一次，返回值恒为 0 或 1。

错误写法：终点判定写在入队处并返回 answer + 1 → 用例 $n = 1$（起点即终点，m = 1），起点从未经过入队判定，队列耗尽后返回 -1，而期望是 0。

错误写法：vis 数组大小开成 m 而不是 m + 1 → 编号从 1 到 $m$，访问 vis[m] 时越界抛异常。

相似题目

题目	难度	考察点
127. 单词接龙	困难	顶点是单词，邻接关系需要用通配符桶构造，返回的是节点数而非边数
433. 最小基因变化	中等	顶点集由基因库显式给出，邻接关系是汉明距离为 1，不涉及坐标换算
542. 01 矩阵	中等	多源 BFS，需要把所有 0 一次性作为第 0 层入队
752. 打开转盘锁	中等	每位数字可正反转动共 8 个邻居，还要把死亡列表并进访问集合
773. 滑动谜题	困难	状态是棋盘排列，必须序列化成字符串才能做访问标记
854. 相似度为 K 的字符串	困难	邻居由交换两位产生，必须只交换第一个失配位来剪枝
994. 腐烂的橘子	中等	多源 BFS，且结束后要回扫是否仍有新鲜橘子来决定返回 -1
1091. 二进制矩阵中的最短路径	中等	八方向移动，且起点终点自身可能是障碍需要先判
1129. 颜色交替的最短路径	中等	状态要扩维记录上一条边的颜色，同一个点会被访问两次
1162. 地图分析	中等	多源 BFS 求最大距离，答案取最后一层的层号
1293. 网格中的最短路径	困难	状态扩维记录剩余可消除障碍数，访问标记是三维的
1298. 你能从盒子里获得的最大糖果数	困难	顶点之间存在钥匙依赖，拿到新钥匙后要回头重查此前打不开的盒子
1345. 跳跃游戏 IV	困难	同值下标互为邻居，展开一次后必须清空该值的邻接表以避免退化
1654. 到家的最少跳跃次数	中等	前进与后退不对称，状态要带「上一步是否后退」，还需自行推导搜索上界
LCP 09. 最小跳跃次数	困难	回退边数量巨大，需维护「已访问的最右前缀」把这类边压成均摊常数
LCR 107. 01 矩阵	中等	可用「两次方向扫描的动态规划」替代 BFS，适合对照两种解法
LCR 108. 单词接龙	困难	适合练双向 BFS，把搜索规模从 $b^d$ 降到 $2b^{d/2}$
LCR 109. 打开转盘锁	中等	适合练双向 BFS 中两侧集合的交换时机与相交判定