Snakes and Ladders

You are given an n x n board labeled from 1 to n^2 in a zigzag pattern. Starting at square 1, you can roll a die (1..6) to move forward. If you land on a square with a ladder or snake (value != -1), you must move to that destination. Return the minimum number of moves to reach square n^2, or -1 if impossible.

Function signature

func SnakesAndLadders(board [][]int) int

Inputs / outputs

• board: n x n with -1 or a destination square number.
• Return: minimum moves to reach n^2, or -1.

Example

board = [
  [-1,-1,-1],
  [-1, 9, 8],
  [-1, 8, 9]
]
Output: 1

Constraints

• 2 <= n <= 20

Core idea (near-solution)

Model squares as nodes in a graph; each node connects to the next 1..6 squares. Use BFS to find the shortest path. A square with a snake/ladder redirects immediately.

Invariant: BFS explores states in non-decreasing number of moves.

Algorithm (step-by-step)

1. Precompute a function that maps square numbers to (r,c) in the zigzag layout.
2. BFS from square 1 with distance 0.
3. For each square, try dice rolls 1..6:
   • Move to next square.
   • If board has a ladder/snake, jump to its destination.
   • If unvisited, enqueue with distance+1.
4. Return distance when reaching n^2, else -1.

Correctness sketch

• Invariant: BFS explores states in non-decreasing number of moves.
• BFS explores nodes in increasing distance from the sources.
• The first time a node is visited is its shortest distance.
• Therefore the recorded distance/level is optimal.

Trace (hand walkthrough)

Example input:
board = [
  [-1,-1,-1],
  [-1, 9, 8],
  [-1, 8, 9]
]
Output: 1

Walk:
- start at 1; try roll=2 -> reach square 3
- square 3 has ladder to 9 -> reach end in 1 move

Pitfalls to avoid

• Incorrect 1D-to-2D mapping for zigzag rows.
• Marking a square visited before applying snake/ladder jump.

Complexity

• Time: O(n^2).
• Extra space: O(n^2).

Implementation notes (Go)

• Convert 1D positions to (row,col) with zigzag row ordering.
• Apply snake/ladder jumps before marking visited.