1057. Snakes and Ladders

Given an n x n board numbered 1..n*n in boustrophedon (snake) order from the bottom-left, where board[r][c] is -1 for a normal cell or the destination square of a snake/ladder, start at square 1 and each move roll to advance 1-6 squares (taking any snake/ladder at the landing square). Return the least number of moves to reach square n*n, or -1 if impossible. The input is JSON {board}.

Input: JSON {board}.

Output: Integer — least 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: Four rolls using ladders.

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

Input: {"board":[[-1,4,-1],[6,-1,5],[-1,3,-1]]}
Output: 2
Explanation: Two moves.

Constraints

• 2<=n<=20

Asked by