Snakes and Ladders
On an N x N board
, the numbers from1
toN*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 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.)
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 rowr
and columnc
has a "snake or ladder" ifboard[r][c] != -1
. The destination of that snake or ladder isboard[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 donotcontinue 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 donotcontinue moving to `4`.)
Return the least number of moves required to reach squareN*N. If it is not possible, return-1
.
Example
Note
比较tricky,先降维(处理的都减1,方便直接跳转),然后在数组里做BFS找到最短路径,每次可以走最多6步,终点是N*N - 1
Code
Last updated