Snakes And Ladders

The square board has labels 1 through n*n. Number its bottom row from left to right, then the next row upward from right to left, alternating direction on each row. For example, on a 3-by-3 board the labels in the top, middle, and bottom rows are [7,8,9], [6,5,4], and [1,2,3].

Start on label 1. In one die roll, choose to advance between 1 and 6 labels without going past n*n. If the cell you land on contains -1, stay there. Otherwise, you must jump to the label stored in that cell. Take at most one such jump per roll, even if the jump destination also contains a jump. Return the fewest rolls needed to reach label n*n, or -1 if it cannot be reached. The first and last labels never start a jump.

Example 1:

Input: board = [[-1,-1,-1],[-1,-1,-1],[-1,-1,-1]]

Output: 2

Explanation: There are no jumps. Advance from label 1 to label 7 on the first roll and from label 7 to label 9 on the second. One roll cannot advance the required 8 labels, so two rolls are necessary.

Example 2:

Input: board = [[-1,-1,-1],[-1,-1,-1],[-1,9,-1]]

Output: 1

Explanation: The bottom-middle cell is label 2 and stores destination 9. Advance one label from 1 to 2, then take that jump to label 9. This reaches the finish in one roll.

Example 3:

Input: board = [[1,1,-1],[1,1,1],[-1,1,1]]

Output: -1

Explanation: Every label reachable from 1 in a single roll sends you back to 1. You can never make progress toward label 9, so return -1.

Constraints:

• 2 <= n <= 20; board has n rows and n columns.
• Each entry is -1 or an integer between 1 and n*n.
• The cells labeled 1 and n*n contain -1.