点击获取AI摘要

909. 蛇梯棋 M

给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n² 编号，编号遵循转行交替方式，从左下角开始 （即，从 board[n - 1][0] 开始）的每一行改变方向。

你一开始位于棋盘上的方格 1。每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：

选定目标方格next，目标方格的编号在范围 [curr + 1, min(curr + 6, n²)]。
- 该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
传送玩家：如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next 。
当玩家到达编号 n² 的方格时，游戏结束。

如果 board[r][c] != -1 ，位于 r 行 c 列的棋盘格中可能存在 “蛇” 或 “梯子”。那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n² 的方格不是任何蛇或梯子的起点。

注意，玩家在每次掷骰的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也不能继续移动。

举个例子，假设棋盘是 [[-1,4],[-1,3]] ，第一次移动，玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ，但不能顺着方格 3 上的梯子前往方格 4 。（简单来说，类似飞行棋，玩家掷出骰子点数后移动对应格数，遇到单向的路径（即梯子或蛇）可以直接跳到路径的终点，但如果多个路径首尾相连，也不能连续跳多个路径）

返回达到编号为 n² 的方格所需的最少掷骰次数，如果不可能，则返回 -1。

示例 1：

snakes

输入：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].length
2 <= n <= 20
board[i][j] 的值是 -1 或在范围 [1, n²] 内
编号为 1 和 n² 的方格上没有蛇或梯子

问题分析

给定一个大小为 $n \times n$ 的棋盘 board，格子按照从 $1$ 到 $n^2$ 编号，编号从左下角开始，每行方向交替（见下图示意）。玩家从编号为 $1$ 的格子开始，每次可以掷骰子向前移动 $1$ 到 $6$ 步，到达编号为 $s$ 的格子后，如果 board 上对应的值不为 $-1$ ，则会被传送到 board 上给定的目的地。目标是最少掷骰子次数到达编号为 $n^2$ 的格子，如果无法到达则返回 $-1$ 。

问题可以抽象为一个状态空间图：

每个编号 $s$ （ $1 \le s \le n^2$ ）表示一个节点。
从节点 $s$ 可以向前连边到节点 $t$ ，其中 $t \in [s+1,\, \min(s+6,\,n^2)]$ ，但是如果节点 $t$ 上有蛇或梯子（即 board[r][c] != -1），那么实际到达的节点是 $\text{dest} = \text{board}[r][c]$ 。
注意：一次掷骰子只能使用一次蛇/梯子，即从 $s \to t$ ，若 $t$ 有传送，直接跳转到目标即可，不可再继续在目标处再次触发。

这样，问题就转化为在该有向图上搜索从节点 $1$ 到节点 $n^2$ 的最短路径长度（每条边表示一次掷骰子）。由于所有边权相同，适合使用广度优先搜索（BFS）。

关键子问题是：如何根据编号 $s$ 快速计算其在二维 board 中的行列 $(r,c)$ 坐标？编号规则如下：

令零基编号： $k = s - 1$ ，则
$\text{quot} = \left\lfloor \frac{k}{n} \right\rfloor,\quad \text{rem} = k \bmod n.$
实际第 $s$ 对应的行索引为
$r = n - 1 - \text{quot}.$
对应列索引 $c$ $c$ 依赖于该行的行号交替方向。因为编号从左往右是第 $n-1$ $n - 1$ 行（零基），下一行要从右往左编号，交替进行。可判断：
- 若 $\text{quot}$ 为偶数，则这一行编号从左往右，对应列索引 $c = \text{rem}$ 。
- 若 $\text{quot}$ 为奇数，则这一行编号从右往左，对应列索引 $c = n - 1 - \text{rem}$ 。

综上，对每个编号 $s$ ，可以 $O(1)$ 映射到 $(r,c)$ 。

算法思路

初始化
- 记棋盘大小为 $n$ ，目标编号为 $N = n^2$ 。
- 使用布尔数组 visited[1..N] 标记编号是否已被访问，初始都为 false。
- 使用队列 queue 存放 BFS 中的当前状态：(编号, 当前掷骰次数)，初始将 (1,\,0) 入队，visited[1]=true。
BFS 遍历
当队列非空时，取出队首状态 $(s,\,d)$ ，表示当前在编号 $s$ ，已经用了 $d$ 次掷骰。
- 若 $s == N$ ，说明到达终点，返回 $d$ 。
- 否则，枚举下一步掷骰可能到达的编号 $t$ ，其中
  $t \in [\,s+1,\;\min(s+6,\,N)\,].$
  对于每一个候选编号 $t$ ，先从编号 $t$ 计算其在 board 上的坐标 $(r,c)$ ，若 board[r][c] != -1，则实际到达编号为 $\text{dest} = \text{board}[r][c]$ ；否则 $\text{dest} = t$ 。
- 若 $\text{dest}$ 未被访问过，则将 $(\text{dest},\,d+1)$ 入队，标记 visited[dest] = true。
结束条件
- 如果 BFS 结束后仍未到达编号 $N$ ，返回 $-1$ 。

由于 BFS 保证第一次访问到编号 $N$ 时，所用掷骰次数即为最少次数。

时间复杂度

总节点数为 $N = n^2$ ；每个节点出队时最多扩展 $6$ 条边（最多向前掷骰 6 种结果）。
因此最坏情况下会访问所有节点，每个节点处理常数次数的边，对应时间复杂度为
$O\bigl(N \times 6\bigr)=O(n^2).$
额外的映射编号到 $(r,c)$ 坐标、检查 visited 等操作均为 $O(1)$ 。
综上，算法总体时间复杂度为 $O(n^2)$ .
空间复杂度主要来自 visited 长度为 $n^2$ ，以及队列大小最多也为 $O(n^2)$ ，所以空间复杂度为 $O(n^2)$ .

代码分解

函数 num_to_pos(s: int, n: int) -> Tuple[int,int]
- 输入：编号 $s$ （ $1 \le s \le n^2$ ）以及棋盘维度 $n$ 。
- 输出：对应的二维坐标 $(r,c)$ 。
- 实现思路：参照“问题分析”中的编号映射公式。
主函数 snakesAndLadders(self, board: List[List[int]]) -> int:
1. 读取 $n = \text{len}(board)$ ，计算 $N = n^2$ 。
2. 初始化 visited = [False] * (N+1)。
3. 初始化双端队列 queue = collections.deque()，并将 (1,0) 入队，visited[1]=True。
4. 当 queue 非空时：
  - 弹出 (s, d)。
  - 若 $s == N$ ，返回 $d$ 。
  - 否则，枚举 $t$ $t$ 从 $s+1$ $s + 1$ 到 $\min(s+6,\,N)$ $min (s + 6, N)$ ：
    1. 先通过 num_to_pos(t, n) 得到 $(r,c)$ ；
    2. 查看 board[r][c]，若不为 $-1$ ，dest = board[r][c]；否则 dest = t。
    3. 若 not visited[dest]，标记并入队 (dest, d+1)。
5. 若遍历结束未返回，则返回 -1。
公式说明
- 设 $s$ 的零基编号为 $k = s - 1$ ，行商 quot = \lfloor k / n \rfloor，余数 rem = k \bmod n。
- 行索引 $r = n - 1 - \text{quot}$ .
- 若 quot 为偶数，列索引 $c = \text{rem};$ $ 否则 $$c = n - 1 - \text{rem}$ .

代码实现

import collections
from typing import List, Tuple

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        """
        使用 BFS 寻找最少掷骰次数从编号 1 到编号 n^2 的路径长度。
        """

        n = len(board)
        N = n * n

        def num_to_pos(s: int) -> Tuple[int, int]:
            """
            将编号 s (1 <= s <= n^2) 映射到 board 上的 (r, c) 坐标。
            行交替方向编号：从左下（编号 1）开始，每行方向交替。
            """
            k = s - 1
            quot, rem = divmod(k, n)
            r = n - 1 - quot
            # 如果 quot 为偶数，该行从左向右编号；否则，从右向左编号
            if quot % 2 == 0:
                c = rem
            else:
                c = n - 1 - rem
            return r, c

        # visited[s] 标记编号 s 是否被访问过
        visited = [False] * (N + 1)
        queue = collections.deque()
        # 从编号 1 开始，掷骰次数为 0
        queue.append((1, 0))
        visited[1] = True

        while queue:
            s, d = queue.popleft()
            # 如果到达目标编号，返回当前掷骰次数
            if s == N:
                return d

            # 枚举下一步掷骰可能到达的编号 t
            for t in range(s + 1, min(s + 6, N) + 1):
                r, c = num_to_pos(t)
                # 如果 board[r][c] != -1，则存在蛇或梯子，跳转到目标编号
                dest = board[r][c] if board[r][c] != -1 else t
                if not visited[dest]:
                    visited[dest] = True
                    queue.append((dest, d + 1))

        # 如果 BFS 结束都未能到达 N，则返回 -1
        return -1