LeetCode 题解工作台
蛇梯棋
给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n 2 编号，编号遵循 转行交替方式 ， 从左下角开始 （即，从 board[n - 1][0] 开始）的每一行改变方向。 你一开始位于棋盘上的方格 1 。每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进： 选定…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们可以使用广度优先搜索的方法，从起点开始，每次向前走 1 到 6 步，然后判断是否有蛇或梯子，如果有，就走到蛇或梯子的目的地，否则就走到下一个方格。 具体地，我们使用一个队列 来存储当前可以到达的方格编号，初始时将编号 放入队列。同时我们使用一个集合 来记录已经到达过的方格，避免重复访问，初始时将编号 加入集合 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循 转行交替方式 ，从左下角开始 （即，从 board[n - 1][0] 开始）的每一行改变方向。
你一开始位于棋盘上的方格 1。每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：
- 选定目标方格
next，目标方格的编号在范围[curr + 1, min(curr + 6, n2)]。- 该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
- 传送玩家：如果目标方格
next处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格next。 - 当玩家到达编号
n2的方格时，游戏结束。
如果 board[r][c] != -1 ，位于 r 行 c 列的棋盘格中可能存在 “蛇” 或 “梯子”。那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格不是任何蛇或梯子的起点。
注意，玩家在每次掷骰的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 不能 继续移动。
- 举个例子，假设棋盘是
[[-1,4],[-1,3]]，第一次移动，玩家的目标方格是2。那么这个玩家将会顺着梯子到达方格3，但 不能 顺着方格3上的梯子前往方格4。（简单来说，类似飞行棋，玩家掷出骰子点数后移动对应格数，遇到单向的路径（即梯子或蛇）可以直接跳到路径的终点，但如果多个路径首尾相连，也不能连续跳多个路径）
返回达到编号为 n2 的方格所需的最少掷骰次数，如果不可能，则返回 -1。
示例 1：
输入：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]] 输出：4 解释： 首先，从方格 1 [第 5 行，第 0 列] 开始。 先决定移动到方格 2 ，并必须爬过梯子移动到到方格 15 。 然后决定移动到方格 17 [第 3 行，第 4 列]，必须爬过蛇到方格 13 。 接着决定移动到方格 14 ，且必须通过梯子移动到方格 35 。 最后决定移动到方格 36 , 游戏结束。 可以证明需要至少 4 次移动才能到达最后一个方格，所以答案是 4 。
示例 2：
输入：board = [[-1,-1],[-1,3]] 输出：1
提示：
n == board.length == board[i].length2 <= n <= 20board[i][j]的值是-1或在范围[1, n2]内- 编号为
1和n2的方格上没有蛇或梯子
解题思路
方法一：BFS
我们可以使用广度优先搜索的方法，从起点开始，每次向前走 1 到 6 步，然后判断是否有蛇或梯子，如果有，就走到蛇或梯子的目的地，否则就走到下一个方格。
具体地，我们使用一个队列 来存储当前可以到达的方格编号，初始时将编号 放入队列。同时我们使用一个集合 来记录已经到达过的方格，避免重复访问，初始时将编号 加入集合 。
在每一次的操作中，我们取出队首的方格编号 ，如果 是终点，那么我们就可以返回当前的步数。否则我们将 向前走 到 步，设新的编号为 ，如果 落在棋盘外，那么我们就直接跳过。否则，我们需要找到 对应的行和列，由于行的编号是从下到上递减的，而列的编号与行的奇偶性有关，因此我们需要进行一些计算得到 对应的行和列。
如果 对应的方格上有蛇或梯子，那么我们需要额外走到蛇或梯子的目的地，设其为 。如果 没有被访问过，我们就将 加入队列和集合中，这样我们就可以继续进行广度优先搜索。
如果我们最终无法到达终点，那么我们就返回 。
时间复杂度 ，空间复杂度 。其中 是棋盘的边长。
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
q = deque([1])
vis = {1}
ans = 0
m = n * n
while q:
for _ in range(len(q)):
x = q.popleft()
if x == m:
return ans
for y in range(x + 1, min(x + 6, m) + 1):
i, j = divmod(y - 1, n)
if i & 1:
j = n - j - 1
i = n - i - 1
z = y if board[i][j] == -1 else board[i][j]
if z not in vis:
vis.add(z)
q.append(z)
ans += 1
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding the BFS strategy is key to solving this problem efficiently.
- question_mark
Candidates should demonstrate the ability to handle dynamic graphs with directed edges (snakes and ladders).
- question_mark
Look for clear reasoning behind the BFS approach and the use of the visited set to avoid revisits.
常见陷阱
外企场景- error
Failing to account for the Boustrophedon layout when processing the board.
- error
Not properly managing the visited array, which can lead to infinite loops or redundant work.
- error
Misunderstanding BFS and using a depth-first search approach, leading to suboptimal solutions.
进阶变体
外企场景- arrow_right_alt
You may be asked to solve the problem with a different board size or more complex variations of the snakes and ladders layout.
- arrow_right_alt
An extended version of the problem may require handling multiple boards in sequence, testing your approach's scalability.
- arrow_right_alt
The problem could introduce additional elements, such as obstacles on the board, that modify how you traverse the squares.