LeetCode 909中等图/BFS
蛇梯棋 图解题解
这道题到底在问什么
给定棋盘 board(board[r][c] 为该格梯子/蛇的目的格号,−1 表示没有)。格子按回行编号:最底行从左到右 1..n,上一行从右到左,如此交替。从 1 号格出发每次掷骰子走 1 到 6,落到有梯子/蛇的格立刻跳到目的格。返回到达 n² 的最少掷骰次数,不可达返回 −1。
- 输入
- n=3,梯子 3→8、蛇 6→1
- 输出
- 2(1 掷到 3 爬梯到 8,再掷到 9)
最优解：一步一步想明白
- 3记住「格号当节点、掷一次骰子连 6 条单位边、BFS 层数就是骰子次数」,下面逐帧套它。
- 4先把棋盘摆好:9 个格按回行编号。注意中间这行 行1 是从右往左数的——最右是 4、中间 5、最左 6,这种「来回蛇形」就是 boustrophedon。
- 5格 3(紫色)装了一架梯子,踩上去会直接爬到格 8。棋盘上把它标成「3↑」,表示这格通到 8。梯子让你一步跨好几格,是抄近路的机会。
- 6格 6(紫色)是一条蛇,踩上去会滑回格 1,标成「6↓」,表示这格滑到 1。蛇会把你打回原地,BFS 自然会绕开这种倒退。
- 7开始 BFS:把起点格 1 放进队列,掷骰次数记 0。队列里(蓝色)是「下一步要从这里掷骰子」的格子。
- 8从队列弹出格 1(紫色),它是「掷 0 次骰子」能站上的格子。接下来掷一次骰子,看能走到哪 6 个格(格 2 到格 7)。
- 9掷出 1 点,走到格 2。格 2 第一次到达,入队(蓝色)、记下掷骰次数 1。
- 10掷出 2 点,踩到格 3、顺梯子爬到格 8。格 8 第一次到达,入队(蓝色)、记下掷骰次数 1。
- 11掷出 3 点,走到格 4。格 4 第一次到达,入队(蓝色)、记下掷骰次数 1。
- 12掷出 4 点,走到格 5。格 5 第一次到达,入队(蓝色)、记下掷骰次数 1。
- 13掷出 5 点,踩到格 6、被蛇滑到格 1。但格 1 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 14掷出 6 点,走到格 7。格 7 第一次到达,入队(蓝色)、记下掷骰次数 1。
- 15从队列弹出格 2(紫色),它是「掷 1 次骰子」能站上的格子。接下来掷一次骰子,看能走到哪 6 个格(格 3 到格 8)。
- 16掷出 1 点,踩到格 3、顺梯子爬到格 8。但格 8 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 17掷出 2 点,走到格 4。但格 4 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 18掷出 3 点,走到格 5。但格 5 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 19掷出 4 点,踩到格 6、被蛇滑到格 1。但格 1 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 20掷出 5 点,走到格 7。但格 7 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 21掷出 6 点,走到格 8。但格 8 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 22从队列弹出格 8(紫色),它是「掷 1 次骰子」能站上的格子。接下来掷一次骰子,只剩格 9 这 1 个落点,再往后就超过终点格 9 了,不能作为落点。
- 23掷出 1 点,走到格 9。格 9 第一次到达,入队(蓝色)、记下掷骰次数 2。
- 24从队列弹出格 4(紫色),它是「掷 1 次骰子」能站上的格子。接下来掷一次骰子,只看格 5 到格 9 这 5 个格,再往后就超过终点格 9 了,不能作为落点。
- 25掷出 1 点,走到格 5。但格 5 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 26掷出 2 点,踩到格 6、被蛇滑到格 1。但格 1 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 27掷出 3 点,走到格 7。但格 7 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 28掷出 4 点,走到格 8。但格 8 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 29掷出 5 点,走到格 9。但格 9 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 30从队列弹出格 5(紫色),它是「掷 1 次骰子」能站上的格子。接下来掷一次骰子,只看格 6 到格 9 这 4 个格,再往后就超过终点格 9 了,不能作为落点。
- 31掷出 1 点,踩到格 6、被蛇滑到格 1。但格 1 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 32掷出 2 点,走到格 7。但格 7 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 33掷出 3 点,走到格 8。但格 8 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 34掷出 4 点,走到格 9。但格 9 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 35从队列弹出格 7(紫色),它是「掷 1 次骰子」能站上的格子。接下来掷一次骰子,只看格 8 到格 9 这 2 个格,再往后就超过终点格 9 了,不能作为落点。
- 36掷出 1 点,走到格 8。但格 8 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 37掷出 2 点,走到格 9。但格 9 之前已经入过队(灰/蓝),再走就是绕路,直接跳过。
- 38弹出的就是终点格 9!
- 39BFS 第一次弹出终点格 9,此刻的层数就是答案:最少掷 2 次骰子(路线:格 1 掷到格 3 爬梯到格 8,再掷一次到格 9)。回头看,我们只是把棋盘当成图、每掷一次骰子算一层、做一遍 BFS,第一次到终点的层数即最短。
⚠️ 容易写错的地方
✗ 错：回行编号算错行列
✓ 对：偶数 r 用列 c、奇数 r 用 n−1−c,行号 n−1−r
编号是来回蛇形的,不处理翻转就会把格号映射到错误的格,蛇梯全错位
✗ 错：入队时不标 seen,出队才标
✓ 对：入队那一刻就加入 seen
只在出队标记,同一个格可能被多条路径重复入队、层数被放大,甚至超时
✗ 错：梯子/蛇连跳
✓ 对：落到目的格 z 后不再继续跳
题目规定一次移动最多用一次蛇或梯,所以落到 z 后即使 z 上还有蛇梯也不再连跳——这是规则决定的,跟目的格本身有没有蛇梯无关
完整代码（Python / C++ / Java）
Python
from typing import List
from collections import deque
class 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 -1C++
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size(), target = n * n;
auto coord = [&](int x) {
int r = (x - 1) / n, c = (x - 1) % n;
return pair<int,int>{n - 1 - r, (r % 2 == 0) ? c : n - 1 - c};
};
queue<pair<int,int>> q;
vector<int> seen(target + 1);
q.push({1, 0}); seen[1] = 1;
while (!q.empty()) {
auto [x, d] = q.front(); q.pop();
if (x == target) return d;
for (int y = x + 1; y <= min(x + 6, target); ++y) {
auto [r, c] = coord(y);
int z = board[r][c] == -1 ? y : board[r][c];
if (!seen[z]) { seen[z] = 1; q.push({z, d + 1}); }
}
}
return -1;
}
};Java
import java.util.*;
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length, target = n * n;
boolean[] seen = new boolean[target + 1];
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{1, 0}); seen[1] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
if (cur[0] == target) return cur[1];
for (int y = cur[0] + 1; y <= Math.min(cur[0] + 6, target); y++) {
int[] rc = coord(y, n);
int z = board[rc[0]][rc[1]] == -1 ? y : board[rc[0]][rc[1]];
if (!seen[z]) { seen[z] = true; q.offer(new int[]{z, cur[1] + 1}); }
}
}
return -1;
}
private int[] coord(int x, int n) {
int r = (x - 1) / n, c = (x - 1) % n;
return new int[]{n - 1 - r, r % 2 == 0 ? c : n - 1 - c};
}
}复杂度
时间
O(n²)
棋盘共 n² 个格,每个格只入队、出队一次;每次出队最多掷 6 个方向,是常数。合计与格子总数 n² 成正比
空间
O(n²)
seen 集合与队列最多装下所有 n² 个格;coord 是 O(1) 换算、不额外建图
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 蛇梯棋 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不真的建出图、而是边走边算邻居?+
正是本解的做法。我们没有显式建邻接表,而是在 BFS 弹出格 x 时,临时算出它的 6 个邻居 x+1..x+6(再经 coord 查蛇梯),这叫「隐式图 BFS」。省下建图的空间,邻居关系由规则即时生成。
如果一次移动允许蛇梯连环跳,代码要怎么改?+
把「z = board[落点] 或落点」改成一个循环:只要新落到的格还有蛇梯就继续跳,直到落到一个 −1 的格为止,再判重入队。原题规则是一次移动不连跳,所以当前代码只解析落点的一次蛇梯;只有变体允许连环跳时才需要这个循环跟随。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 蛇梯棋 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。