Snakes and Ladders
Last updated
Last updated
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 start on square1
of the board (which is always in the last row and first column). Each move, starting from squarex
, consists of the following:
You choose a destination squareS
with number x+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.)
IfS
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
.
比较tricky,先降维(处理的都减1,方便直接跳转),然后在数组里做BFS找到最短路径,每次可以走最多6步,终点是N*N - 1