| 1 | class Solution: |
| 2 | def snakesAndLadders(self, board: List[List[int]]) -> int: |
| 3 | length = len(board) |
| 4 | board.reverse() |
| 5 | |
| 6 | def intToPos(square): |
| 7 | r = (square - 1) // length |
| 8 | c = (square - 1) % length |
| 9 | if r % 2: |
| 10 | c = length - 1 - c |
| 11 | return [r, c] |
| 12 | |
| 13 | q = deque() |
| 14 | q.append([1, 0]) # [square, moves] |
| 15 | visit = set() |
| 16 | while q: |
| 17 | square, moves = q.popleft() |
| 18 | for i in range(1, 7): |
| 19 | nextSquare = square + i |
| 20 | r, c = intToPos(nextSquare) |
| 21 | if board[r][c] != -1: |
| 22 | nextSquare = board[r][c] |
| 23 | if nextSquare == length * length: |
| 24 | return moves + 1 |
| 25 | if nextSquare not in visit: |
| 26 | visit.add(nextSquare) |
| 27 | q.append([nextSquare, moves + 1]) |
| 28 | return -1 |