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
- BFS over the square numbers, since every move has cost 1.
- 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). - A snake or ladder is applied immediately and without consuming a move.
- 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.