DSA · Graph / BFS · #166
Snakes and Ladders
Module 76 · difficulty 3/5·⏱ 30:00starts on first keystroke
You are given an `n x n` integer matrix `board` where the squares are labeled `1` to `n*n` in a **Boustrophedon (snake) order**: starting at the **bottom-left** square (label `1`), the labels alternate direction row by row as you move upward. You start on square `1`. On each move, from square `curr` you may pick any destination `next` with `curr + 1 <= next <= min(curr + 6, n*n)` (a standard die roll). If `board[r][c]` of square `next` is **not** `-1`, you immediately move to that snake/ladder destination instead (only once per move — you do **not** chain). Return the **least number of moves** required to reach square `n*n`, or `-1` if it is unreachable. Implement `function snakesAndLadders(board)`.
Examples
board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]→4— 1 -> 2 (ladder to 15) -> 17 -> 13 (ladder to 35) -> 36. Four moves.board = [[-1,-1],[-1,3]]→1— Square 1 is bottom-left; one die roll reaches square 4 = n*n.board = [[-1,4,-1],[6,2,6],[-1,3,-1]]→2— Two moves via ladders to reach square 9.
Constraints
- · n == board.length == board[i].length
- · 2 <= n <= 20
- · board[i][j] is -1 or in the range [1, n*n]
- · The squares labeled 1 and n*n do not have a snake or ladder
- · A square may not have a snake/ladder that points back to itself
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.