0909. Snakes and Ladders

题目信息

题号:

0909

难度:

Medium

主题:

棋盘、最少移动次数、强制跳转

原题:

LeetCode 0909

重点:

棋盘从左下角开始按每行方向交替的牛耕式顺序编号;一次掷骰后至多触发当前落点上的一次蛇或梯子跳转

题目重述

给定 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 格即可直接到达终点,因此最少只需一次移动。