Snakes and Ladders
An n x n board holds the squares 1..n^2 in boustrophedon order: square 1 is the bottom-left cell, numbers increase to the right along the bottom row, then the next row up runs right to left, and so on, alternating.
A cell value of -1 is an ordinary square. Any other value d is a snake or ladder that sends you to square d. You start on square 1 (any jump on it is ignored). On each move you roll a die of 1 to 6 and may move to any of the squares cur + 1 .. cur + 6 (up to n^2); if the square you land on has a jump, you must take it, but you take at most one jump per move, so a jump's destination is not jumped again.
Return the fewest moves needed to reach square n^2, or -1 if it cannot be reached.
Example 1
- Input
- board = [[-1,-1,-1],[-1,9,8],[-1,8,9]]
- Output
- 1
- Why
- Rolling 2 from square 1 lands on square 3, which is a ladder to 9.
Example 2
- Input
- board = [[-1,-1],[-1,3]]
- Output
- 1
- Why
- Roll 3 from square 1 to land directly on square 4.
Constraints
- 1 <= n <= 20
- board[i][j] is -1 or in [1, n^2]
- Squares 1 and n^2 have no jump.
Hints
Give it a real attempt first. Run shows which examples fail.