Description
You are given an n x n integer matrix board where the cells are labeled from 1 to n² in a Boustrophedon style starting from the bottom left of the board. You start on square 1 of the board. In each move, starting from square curr, you pick a destination square next with label in the range [curr + 1, min(curr + 6, n²)]. If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next. The game ends when you reach square n². A board square with value -1 has no snake or ladder. Return the least number of moves required to reach square n², or -1 if not possible.
Examples
board = [[-1,-1,-1],[-1,9,-1],[-1,-1,-1]]1From square 1, land on square 2 which has a ladder to square 9 (the last square).
board = [[-1,-1],[-1,-1]]1Board is 2x2, from square 1 it is possible to reach square 4 directly.
Constraints
- •
n == board.length == board[i].length - •
2 ≤ n ≤ 20 - •
board[i][j] is either -1 or in the range [1, n²]