Snakes and Ladders
On an N x N board
, the numbers from 1
to N*N
are written boustrophedonically starting from the bottom left of the board, and alternating direction each row. For example, for a 6 x 6 board, the numbers are written as follows:
You start on square 1
of the board (which is always in the last row and first column). Each move, starting from square x
, consists of the following:
You choose a destination square
S
with numberx+1
,x+2
,x+3
,x+4
,x+5
, orx+6
, provided this number is<= N*N
.(This choice simulates the result of a standard 6-sided die roll: ie., there are always at most 6 destinations, regardless of the size of the board.)
If
S
has a snake or ladder, you move to the destination of that snake or ladder. Otherwise, you move toS
.
A board square on row r
and column c
has a "snake or ladder" if board[r][c] != -1
. The destination of that snake or ladder is board[r][c]
.
Note that you only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving. (For example, if the board is `[[4,-1],[-1,3]]`, and on the first move your destination square is `2`, then you finish your first move at `3`, because you do not continue moving to `4`.)
Return the least number of moves required to reach square N*N. If it is not possible, return -1
.
Example 1:
Note:
2 <= board.length = board[0].length <= 20
board[i][j]
is between1
andN*N
or is equal to-1
.The board square with number
1
has no snake or ladder.The board square with number
N*N
has no snake or ladder.
Last updated