Snakes and Ladders
Medium · Stack & Strings · Array · Breadth-First Search · Matrix
Problem
You are given an n x n board. Its squares are numbered 1 to n² in a zigzag: starting at the bottom-left corner, row by row upward, with the direction alternating each row (left to right on the bottom row, right to left on the next, and so on).
You start on square 1. On each move from square curr:
- Pick a destination next in [curr + 1, min(curr + 6, n²)], any outcome of a six-sided die.
- If the board cell for next holds a value other than -1, it is the start of a snake or ladder and you move to the square with that number. You follow at most one snake or ladder per move, even if it drops you on the start of another.
Squares 1 and n² never hold a snake or ladder. Return the fewest moves needed to reach square n², or -1 if it cannot be reached.
Examples
Input: board = [[-1,-1,-1],[-1,9,-1],[-1,-1,-1]] Output: 1
The middle cell is square 5, whose ladder goes to 9: rolling a 4 wins in one move.
Input: board = [[-1,-1],[-1,3]] Output: 1
Square 4 is reached directly with a roll of 3.
Input: board = [[-1,-1,-1],[-1,-1,-1],[-1,-1,-1]] Output: 2
With no shortcuts, square 9 takes two rolls, for example 1 to 3 to 9.
Constraints
- n == len(board) == len(board[i])
- 2 <= n <= 20
- board[i][j] is -1 or in [1, n²]
- squares 1 and n² have no snake or ladder
Approaches
- Relax every square until nothing changes — time O(n⁴), space O(n²)
Follow-up
What if the die were loaded, and you wanted the expected number of moves under a fixed strategy instead of the best case? Then each square’s value depends on the average of its six successors, which is a system of linear equations (or value iteration until the numbers settle), not a BFS. BFS works here only because every move costs exactly one and you choose the roll.
Related problems
Start free on Cariara · Coding problems · System design studio
