LeetCode 909. 蛇梯棋 题目描述 你得到一块大小为 n x n 的方形棋盘，行和列都从 1 开始编号，编号规则遵循“之”字形（蛇形）顺序： 从棋盘左下角（第 n 行，第 1 列）开始，编号为 1。 每一行交替从左到右、从右到左编号，例如 n=3 时棋盘编号如下： 7 8 9 6 5 4 1 2 3 棋盘上有一些“蛇”或“梯子”，用一个长度为 n² 的二维数组 board 表示，其中 board[i][j] 表示编号为 i*n + j + 1 的格子的目标： 如果 board[i][j] != -1 ，则该格子是蛇或梯子，玩家会立即移动到编号为 board[i][j] 的格子。 如果 board[i][j] == -1 ，则无特殊事件。 玩家从编号 1 的格子出发，每次可以掷一个标准的 6 面骰子，根据点数移动到编号当前+1 到 +6 的格子。如果目标格子超出 n²，则不能移动。如果目标格子是蛇或梯子，则立即传送到对应编号的格子。 请你返回到达编号 n² 的格子所需的最少移动次数。如果无法到达，返回 -1。 解题过程 步骤 1：问题理解与建模 此题可抽象为在 1 到 n² 的编号序列上进行最短路径搜索。每个编号格子是一个节点，每次掷骰子 1~6 点相当于从当前节点可以向前走 1 到 6 步（但不能超出 n²），如果目标节点有蛇或梯子，则直接跳到蛇/梯子指向的节点。这本质上是一个 带传送的有向无权图的最短路径 问题，因为每次移动（无论是否传送）都算一步，边权为 1，适合用 BFS 求解。 步骤 2：编号与坐标转换 因为棋盘编号是蛇形顺序，且输入是二维数组 board ，我们需要实现两个辅助函数： 给定编号 num ，求其在棋盘上的行列坐标 (r, c)。 给定坐标 (r, c)，求编号（但本题中 BFS 时直接用编号操作更方便，只需在遇到蛇/梯子时用坐标读取 board 值）。 转换规则： 编号从 1 到 n²。 行索引从下往上为 0 到 n-1（即输入数组的第 0 行是棋盘最下面一行）。 设编号为 label ，先求 label-1 的零基值 zero = label - 1 。 行号 r = n - 1 - zero / n 。 列号： 判断该行是从左到右还是从右到左：如果 (n-1-r) 为偶数，则该行编号从左到右（因为最下面一行是 r=n-1，对应 n-1-r=0 偶数）；否则从右到左。 从左到右时， c = zero % n 。 从右到左时， c = n - 1 - zero % n 。 步骤 3：BFS 设计 队列存储当前编号。 用集合或数组记录已访问的编号，避免重复访问。 从 1 开始，每次取出节点，尝试掷骰子 1~6 得到下一个编号 nxt ，如果 nxt > n*n 则忽略。 将 nxt 转换为坐标 (r, c)，检查 board[r][c] ： 如果 board[r][c] != -1 ，则 nxt 更新为该值（传送）。 如果 nxt 等于 n²，返回当前步数 +1。 如果 nxt 未访问过，标记并加入队列。 步骤 4：边界与细节 注意编号 1 位置也可能有梯子/蛇，但题目从 1 开始，不会一开始就传送。 如果队列为空还未到达 n²，返回 -1。 已访问标记要在入队时立即标记，防止同一层多次访问同一节点导致重复入队。 步骤 5：举例说明 以 n=3, board = [ [ -1,-1,-1],[ -1,-1,-1],[ -1,-1,-1] ] 为例： 棋盘编号如前述。 BFS 过程： 起点 1，掷 1~6 可到 2~7，但超出 9 的忽略。 从 1 到 2：2 坐标 (2,1)，board=-1，到达 2。 … 最终找到 9 的最短路径。 步骤 6：时间复杂度 每个节点最多访问一次，每次尝试 6 个骰子结果，时间复杂度 O(6 * n²) = O(n²)，空间复杂度 O(n²)。