题目描述
思路解析动画文字版
记住「格号当节点、掷一次骰子连 6 条单位边、BFS 层数就是骰子次数」,下面逐帧套它。
先把棋盘摆好:9 个格按回行编号。注意中间这行 行1 是从右往左数的——最右是 4、中间 5、最左 6,这种「来回蛇形」就是 boustrophedon。
格 3(紫色)装了一架梯子,踩上去会直接爬到格 8。棋盘上把它标成「3↑」,表示这格通到 8。梯子让你一步跨好几格,是抄近路的机会。
格 6(紫色)是一条蛇,踩上去会滑回格 1,标成「6↓」,表示这格滑到 1。蛇会把你打回原地,BFS 自然会绕开这种倒退。
开始 BFS:把起点格 1 放进队列,掷骰次数记 0。队列里(蓝色)是「下一步要从这里掷骰子」的格子。
从队列弹出格 1(紫色),它是「掷 0 次骰子」能站上的格子。接下来掷一次骰子,看能走到哪 6 个格(格 2 到格 7)。
掷出 1 点,走到格 2。格 2 第一次到达,入队(蓝色)、记下掷骰次数 1。
掷出 2 点,踩到格 3、顺梯子爬到格 8。格 8 第一次到达,入队(蓝色)、记下掷骰次数 1。
掷出 3 点,走到格 4。格 4 第一次到达,入队(蓝色)、记下掷骰次数 1。
掷出 4 点,走到格 5。格 5 第一次到达,入队(蓝色)、记下掷骰次数 1。
掷出 5 点,踩到格 6、被蛇滑到格 1。但格 1 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 6 点,走到格 7。格 7 第一次到达,入队(蓝色)、记下掷骰次数 1。
从队列弹出格 2(紫色),它是「掷 1 次骰子」能站上的格子。接下来掷一次骰子,看能走到哪 6 个格(格 3 到格 8)。
掷出 1 点,踩到格 3、顺梯子爬到格 8。但格 8 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 2 点,走到格 4。但格 4 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 3 点,走到格 5。但格 5 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 4 点,踩到格 6、被蛇滑到格 1。但格 1 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 5 点,走到格 7。但格 7 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 6 点,走到格 8。但格 8 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
从队列弹出格 8(紫色),它是「掷 1 次骰子」能站上的格子。接下来掷一次骰子,只剩格 9 这 1 个落点,再往后就超过终点格 9 了,不能作为落点。
掷出 1 点,走到格 9。格 9 第一次到达,入队(蓝色)、记下掷骰次数 2。
从队列弹出格 4(紫色),它是「掷 1 次骰子」能站上的格子。接下来掷一次骰子,只看格 5 到格 9 这 5 个格,再往后就超过终点格 9 了,不能作为落点。
掷出 1 点,走到格 5。但格 5 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 2 点,踩到格 6、被蛇滑到格 1。但格 1 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 3 点,走到格 7。但格 7 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 4 点,走到格 8。但格 8 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 5 点,走到格 9。但格 9 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
从队列弹出格 5(紫色),它是「掷 1 次骰子」能站上的格子。接下来掷一次骰子,只看格 6 到格 9 这 4 个格,再往后就超过终点格 9 了,不能作为落点。
掷出 1 点,踩到格 6、被蛇滑到格 1。但格 1 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 2 点,走到格 7。但格 7 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 3 点,走到格 8。但格 8 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 4 点,走到格 9。但格 9 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
从队列弹出格 7(紫色),它是「掷 1 次骰子」能站上的格子。接下来掷一次骰子,只看格 8 到格 9 这 2 个格,再往后就超过终点格 9 了,不能作为落点。
掷出 1 点,走到格 8。但格 8 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
掷出 2 点,走到格 9。但格 9 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
弹出的就是终点格 9!
BFS 第一次弹出终点格 9,此刻的层数就是答案:最少掷 2 次骰子(路线:格 1 掷到格 3 爬梯到格 8,再掷一次到格 9)。回头看,我们只是把棋盘当成图、每掷一次骰子算一层、做一遍 BFS,第一次到终点的层数即最短。
边界:一步可达返回 1、走不到返回 −1、梯子能抄近路。
两个追问:隐式图 BFS 不必建图;连环跳则在落点处循环跟蛇梯。
参考代码
from typing import Listfrom collections import dequeclass Solution: def snakesAndLadders(self, board: List[List[int]]) -> int: n = len(board) def coord(x): r = (x - 1) // n c = (x - 1) % n row = n - 1 - r col = c if r % 2 == 0 else n - 1 - c return row, col seen = {1} q = deque([(1, 0)]) while q: x, d = q.popleft() if x == n * n: return d for y in range(x + 1, min(x + 6, n * n) + 1): r, c = coord(y) z = board[r][c] if board[r][c] != -1 else y if z not in seen: seen.add(z) q.append((z, d + 1)) return -1复杂度
- 时间：O(n²)，棋盘共 n² 个格,每个格只入队、出队一次;每次出队最多掷 6 个方向,是常数。合计与格子总数 n² 成正比
- 空间：O(n²)，seen 集合与队列最多装下所有 n² 个格;coord 是 O(1) 换算、不额外建图
易错点
面试追问把动画讲成自己的话
追问能不能不真的建出图、而是边走边算邻居?
追问如果一次移动允许蛇梯连环跳,代码要怎么改?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最短的桥
LeetCode 934 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题