Snakes and Ladders

Medium#909states

A square board of n × n squares is numbered from 1 in the bottom-left corner: along the bottom row, then back along the next row, like a snake. Some squares start a ladder or a snake that moves you to another square. You start on square 1, and one move is a roll of a die: you go 1 to 6 squares ahead and, if you land where a ladder or a snake starts, follow it (only one per move). Find the fewest moves to reach square n × n, or -1 if you never can. Our example: a 4 × 4 board with a ladder from 2 to 11 and a snake from 14 to 4 — the answer is 2.

909 Snakes and LaddersWalkthrough · 1×

Example: the fewest die rolls from square 1 to 16 on a 4 × 4 board with a ladder 2 → 11 and a snake 14 → 4.

12345678910111213141516snake 14 → 4ladder 2 → 11queuefront on the left—
not reachedwaiting in the queuecurrent squarewhere the roll takes youdone

You start on square 1: 0 moves

01/38
restart · back · play · step
Speed
1function snakesAndLadders(board):
2 dist = {1: 0}
3 queue = [1]
4 while queue is not empty:
5 square = queue.popFront()
6 for next in squaresAfterRoll(square):
7 if next == n * n: // the last square
8 return dist[square] + 1
9 if next not in dist:
10 dist[next] = dist[square] + 1
11 queue.pushBack(next)
12 return -1
state
dist
{1: 0}
queue
–
square
–
next
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A square is a state and a roll is an edge, so every move costs the same: BFS takes squares in order of moves, and the first time it reaches the last square is the fewest moves.
  2. The ladder or snake is followed before the square is stored, because you end the move where it takes you: landing on 2 means standing on 11.
  3. A square already in dist was reached in as few moves or fewer, so it is skipped and nothing is queued twice.

Complexity

Time O(n²): each of the n² squares is queued at most once and tries at most 6 rolls. Memory O(n²) for dist and the queue.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.