-
Notifications
You must be signed in to change notification settings - Fork 2.5k
Expand file tree
/
Copy path0909-snakes-and-ladders.py
More file actions
28 lines (26 loc) · 912 Bytes
/
0909-snakes-and-ladders.py
File metadata and controls
28 lines (26 loc) · 912 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
length = len(board)
board.reverse()
def intToPos(square):
r = (square - 1) // length
c = (square - 1) % length
if r % 2:
c = length - 1 - c
return [r, c]
q = deque()
q.append([1, 0]) # [square, moves]
visit = set()
while q:
square, moves = q.popleft()
for i in range(1, 7):
nextSquare = square + i
r, c = intToPos(nextSquare)
if board[r][c] != -1:
nextSquare = board[r][c]
if nextSquare == length * length:
return moves + 1
if nextSquare not in visit:
visit.add(nextSquare)
q.append([nextSquare, moves + 1])
return -1