1
class Solution:
2
    def snakesAndLadders(self, board: List[List[int]]) -> int:
3
        n = len(board)
4
        moves = 0
5
        q = collections.deque([1])
6
        visited = [[False for _ in range(n)] for _ in range(n)]
7
        visited[n - 1][0] = True
8
        while q:
9
            size = len(q)
10
            for i in range(size):
11
                currBoardVal = q.popleft()
12
                if currBoardVal == n * n:
13
                    return moves
14
                for diceVal in range(1, 7):
15
                    if currBoardVal + diceVal > n * n:
16
                        break
17
                    pos = self.findCoordinates(currBoardVal + diceVal, n)
18
                    row, col = pos
19
                    if not visited[row][col]:
20
                        visited[row][col] = True
21
                        if board[row][col] == -1:
22
                            q.append(currBoardVal + diceVal)
23
                        else:
24
                            q.append(board[row][col])
25
            moves += 1
26
        return -1
27

28
    def findCoordinates(self, curr: int, n: int) -> Tuple[int, int]:
29
        row = n - (curr - 1) // n - 1
30
        col = (curr - 1) % n
31
        if row % 2 == n % 2:
32
            return (row, n - 1 - col)
33
        else:
34
            return (row, col)