Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each dice roll is one equal-cost graph edge, including any single snake or ladder it triggers. Breadth-first search therefore finds the minimum number of rolls. The state is the square where a turn ends, not the intermediate square before the forced jump.

Approach

Start a queue with square one and distance zero. Convert a square label to board coordinates by counting rows upward from the bottom and reversing columns on every other row.
For each dequeued square, try the next one through six labels without passing the board's final label.
Apply the destination square's snake or ladder once, if present. Do not chain another jump during the same roll.
Return the current distance plus one if the resulting square is the goal. Otherwise enqueue unseen resulting squares with that distance.
Return -1 if the queue empties; visited states prevent cycles from causing an infinite search.

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)

        def get_pos(x):
            r = n - ((x - 1) // n) - 1
            if (n - r - 1) % 2 == 0:
                c = (x - 1) % n
            else:
                c = n - ((x - 1) % n) - 1
            return r, c

        q = deque([(1, 0)])  # node, dist
        seen = set()

        while q:
            node, dist = q.popleft()
            for x in range(1, 7):
                if node + x > n**2:
                    break
                next = node + x
                i, j = get_pos(next)
                if board[i][j] != -1:
                    next = board[i][j]
                if next == n**2:
                    return dist + 1
                if not next in seen:
                    seen.add(next)
                    q.append((next, dist + 1))

        return -1

Complexity analysis

An n × n board has N = n² states and at most six outgoing dice moves per state. Breadth-first search therefore uses O(N) time and O(N) auxiliary space.