0909. Snakes and Ladders¶
题目信息¶
- 题号:
0909
- 难度:
Medium
- 主题:
棋盘、最少移动次数、强制跳转
- 原题:
- 重点:
棋盘从左下角开始按每行方向交替的牛耕式顺序编号;一次掷骰后至多触发当前落点上的一次蛇或梯子跳转
题目重述¶
给定 n x n 方形数组 board。棋盘格编号从 1 到 n^2:编号 1 位于左下角,底行从左向右递增,上一行改为从右向左,之后逐行交替方向。
你从编号 1 开始。每次移动可选择前进 1 至 6 格,但不能超过 n^2。若落到的格子对应数组值不是 -1,必须立即跳到该值指定的编号;一次移动只执行这一次跳转,即使跳转后的格子也有蛇或梯子也不会继续连跳。
请返回到达编号 n^2 所需的最少移动次数;若无法到达,返回 -1。2 <= n <= 20,格子值为 -1 或 [1, n^2] 内的编号。
自建示例¶
一步通过梯子到达终点:
输入:board = [[-1,-1,-1],[-1,-1,-1],[-1,9,-1]]
输出:1
解释:3 x 3 棋盘的底行编号依次为 1、2、3。第一次选择前进到编号 2,该格的梯子直接把棋子送到终点 9。
最小棋盘没有蛇或梯子:
输入:board = [[-1,-1],[-1,-1]]
输出:1
解释:棋盘终点编号为 4。从编号 1 一次前进 3 格即可直接到达终点,因此最少只需一次移动。