⚡Flashcard Drill➔
NeetCode #572LC-909MediumGraphs
← Back to All Problems

#572 · #909 · Snakes and Ladders(蛇梯棋)

📌 Problem Statement & Constraints

You are given an n x n board representing a Snakes and Ladders board, numbered boustrophedon from the bottom-left. From square s you move to any of s+1 .. s+6; if that square has a snake or ladder (!= -1), you move to its destination. Return the minimum moves to reach square n^2, or -1. Constraints: 2 <= n <= 20.

💡 Core Algorithmic Approaches

  1. BFS over the square numbers, since every move has cost 1.
  2. Convert a square number to board coordinates: q, r = divmod(s - 1, n), with the row reversed and the column reversed on alternate rows (boustrophedon).
  3. A snake or ladder is applied immediately and without consuming a move.
  4. The BFS naturally gives the minimum number of dice rolls.

💻 Benchmark Python3 Implementation

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

        def coords(s: int):
            q, r = divmod(s - 1, n)        # q-th row from the bottom, offset r
            row = n - 1 - q
            col = r if q % 2 == 0 else n - 1 - r   # boustrophedon
            return row, col

        dist = {1: 0}
        q = deque([1])
        while q:
            s = q.popleft()
            if s == n * n:
                return dist[s]
            for nxt in range(s + 1, min(s + 6, n * n) + 1):
                r, c = coords(nxt)
                dest = board[r][c] if board[r][c] != -1 else nxt
                if dest not in dist:
                    dist[dest] = dist[s] + 1
                    q.append(dest)
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2 * 6) = O(n^2): at most n^2 squares, each with 6 moves.
💾 Space Complexity
O(n^2) for the distance map and the queue.

⚠️ Interview Pitfalls & Follow-ups

  • Getting the boustrophedon mapping wrong: even rows (0-indexed from the bottom) go left to right, odd rows right to left.
  • Counting the snake/ladder as a move: the jump is free.
  • Recording the distance for the pre-jump square: only the destination matters.
  • Using DFS: it does not guarantee the minimum number of rolls.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems