647. Snakes and Ladders

Given an n x n board numbered in boustrophedon (zigzag) order from 1 at the bottom-left to n*n, where a cell value of -1 means no snake or ladder and any other value is the destination square, return the least number of dice moves (1-6 each) to reach square n*n from square 1, or -1 if impossible. The input is JSON {board}.

Input: JSON {board}.

Output: Integer — the minimum moves, or -1.

Examples

Input: {"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]]}
Output: 4
Explanation: Ladders shorten the path to 4 moves.

Input: {"board":[[-1,-1],[-1,3]]}
Output: 1
Explanation: One move reaches the end.

Input: {"board":[[-1,-1,-1],[-1,-1,-1],[-1,-1,-1]]}
Output: 2
Explanation: Two dice rolls.

Constraints

• 2<=n<=20

Asked by