0909. 蛇梯棋

ITCharge大约 4 分钟

---

0909. 蛇梯棋

标签：广度优先搜索、数组、矩阵
难度：中等

题目链接

0909. 蛇梯棋 - 力扣

题目大意

描述：

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

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

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

如果 $board[r][c] \ne -1$ ，位于 $r$ 行 $c$ 列的棋盘格中可能存在「蛇」或「梯子」。那个蛇或梯子的目的地将会是 $board[r][c]$ 。编号为 1 和 $n^2$ 的方格不是任何蛇或梯子的起点。

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

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

要求：

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

说明：

$n == board.length == board[i].length$ 。
$2 \le n \le 20$ 。
$board[i][j]$ 的值是 -1 或在范围 $[1, n^2]$ 内。
编号为 1 和 $n^2$ 的方格上没有蛇或梯子。

示例：

示例 1：

![](https://assets.leetcode.com/uploads/2018/09/23/snakes.png)

输入：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

解题思路

思路 1：广度优先搜索

这道题是一个典型的最短路径问题，可以使用广度优先搜索（BFS）来解决。

坐标转换：首先需要将编号转换为二维坐标。由于棋盘是"牛耕式转行"编号，即奇数行从左到右，偶数行从右到左。
BFS 搜索：从方格 $1$ 开始，每次可以移动 $1 \sim 6$ 步（模拟掷骰子），如果目标方格有蛇或梯子，则传送到对应位置。
记录步数：使用队列记录当前位置和步数，使用集合记录已访问的方格，避免重复访问。
终止条件：当到达方格 $n^2$ 时，返回当前步数。

思路 1：代码

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        
        # 将编号转换为坐标
        def num_to_pos(num):
            num -= 1  # 转换为 0 索引
            row = n - 1 - num // n  # 从下往上
            col = num % n
            # 奇数行（从下往上数）需要反转列
            if (n - 1 - row) % 2 == 1:
                col = n - 1 - col
            return row, col
        
        # BFS
        queue = collections.deque([(1, 0)])  # (当前位置, 步数)
        visited = {1}
        
        while queue:
            curr, steps = queue.popleft()
            
            # 尝试掷骰子 1-6
            for i in range(1, 7):
                next_num = curr + i
                if next_num > n * n:
                    break
                
                # 获取目标位置
                row, col = num_to_pos(next_num)
                # 如果有蛇或梯子，传送到目标位置
                if board[row][col] != -1:
                    next_num = board[row][col]
                
                # 到达终点
                if next_num == n * n:
                    return steps + 1
                
                # 未访问过则加入队列
                if next_num not in visited:
                    visited.add(next_num)
                    queue.append((next_num, steps + 1))
        
        return -1

思路 1：复杂度分析

时间复杂度： $O(n^2)$ ，其中 $n$ 是棋盘的边长。每个方格最多访问一次。
空间复杂度： $O(n^2)$ ，需要使用队列和集合存储访问状态。