# LeetCode 909: Snakes and Ladders

## Problem Restatement

We are given an `n x n` board for a Snakes and Ladders game.

The squares are numbered from `1` to `n^2` in a boustrophedon order. That means the numbering starts from the bottom-left square, goes left to right on one row, then right to left on the next row, alternating direction each row.

From a square `curr`, one dice roll can move to any square from:

```python
curr + 1
```

through:

```python
min(curr + 6, n * n)
```

If the destination square has a snake or ladder, meaning `board[r][c] != -1`, we must move to `board[r][c]`.

A snake or ladder is followed at most once per dice roll. If its destination also has another snake or ladder, we do not follow the second one.

Return the minimum number of dice rolls needed to reach square `n^2`. If it cannot be reached, return `-1`. The official statement defines this one-snake-or-ladder-per-roll rule explicitly.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `board`, an `n x n` integer matrix |
| Output | Minimum number of dice rolls to reach square `n^2` |
| Empty square | `-1` |
| Snake or ladder | `board[r][c]` gives destination square |
| Start | Square `1` |
| Goal | Square `n^2` |

Function shape:

```python
def snakesAndLadders(board: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
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],
]
```

Answer:

```python
4
```

One shortest route is:

```python
1 -> 2 -> 15 -> 17 -> 13 -> 14 -> 35 -> 36
```

This uses four dice rolls. The moves through `15`, `13`, and `35` happen because of ladders or snakes.

Example 2:

```python
board = [
    [-1, -1],
    [-1, 3],
]
```

Answer:

```python
1
```

From square `1`, we can roll to square `2`, then the ladder sends us to square `3`.

We do not immediately follow another snake or ladder after that same roll.

## First Thought: Simulate Greedily

One tempting idea is to always choose the move that lands farthest ahead after applying a snake or ladder.

That does not always work.

A square that moves far ahead may lead into a bad position later. A smaller move may reach a better ladder. Since each dice roll has equal cost, this is a shortest path problem on an unweighted graph.

The right tool is breadth-first search.

## Key Insight

Treat every square as a graph node.

From each square `curr`, there are up to six outgoing edges:

```python
curr -> curr + 1
curr -> curr + 2
...
curr -> curr + 6
```

After choosing a destination, apply one snake or ladder if the board says so.

Since every edge represents exactly one dice roll, all edges have the same cost.

Breadth-first search finds the minimum number of dice rolls.

## Mapping Square Number to Board Cell

The hardest part is converting a square number into `(row, col)`.

Square numbers start from the bottom row.

Let:

```python
q = square - 1
row_from_bottom = q // n
col_in_row = q % n
```

The actual row in the matrix is:

```python
row = n - 1 - row_from_bottom
```

If `row_from_bottom` is even, the row goes left to right.

If `row_from_bottom` is odd, the row goes right to left.

So:

```python
if row_from_bottom % 2 == 0:
    col = col_in_row
else:
    col = n - 1 - col_in_row
```

## Algorithm

Use BFS.

1. Start from square `1`.
2. Put `(1, 0)` into a queue, where `0` is the number of moves used so far.
3. Mark square `1` as visited.
4. While the queue is not empty:
   - Pop the current square and move count.
   - If the current square is `n^2`, return the move count.
   - Try all dice outcomes from `1` to `6`.
   - Convert the candidate square into `(row, col)`.
   - If `board[row][col] != -1`, move to that destination.
   - If the final destination was not visited, mark it and push it into the queue.
5. If BFS ends without reaching `n^2`, return `-1`.

## Correctness

Each BFS edge represents one valid dice roll from the game.

For a chosen next square, the algorithm applies exactly one snake or ladder if present, matching the problem rule.

BFS explores states by increasing number of dice rolls. It visits all squares reachable in `0` rolls, then all squares reachable in `1` roll, then all squares reachable in `2` rolls, and so on.

Therefore, the first time BFS reaches square `n^2`, the move count is the minimum possible number of dice rolls.

If BFS finishes without reaching square `n^2`, then no sequence of legal dice rolls can reach the final square, so returning `-1` is correct.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | Each square is visited at most once, and each visit checks up to six moves |
| Space | `O(n^2)` | The queue and visited set can store board squares |

## Implementation

```python
from collections import deque

class Solution:
    def snakesAndLadders(self, board: list[list[int]]) -> int:
        n = len(board)
        target = n * n

        def get_cell(square: int) -> tuple[int, int]:
            q = square - 1
            row_from_bottom = q // n
            col_in_row = q % n

            row = n - 1 - row_from_bottom

            if row_from_bottom % 2 == 0:
                col = col_in_row
            else:
                col = n - 1 - col_in_row

            return row, col

        queue = deque([(1, 0)])
        visited = {1}

        while queue:
            square, moves = queue.popleft()

            if square == target:
                return moves

            for step in range(1, 7):
                next_square = square + step

                if next_square > target:
                    break

                row, col = get_cell(next_square)

                if board[row][col] != -1:
                    next_square = board[row][col]

                if next_square not in visited:
                    visited.add(next_square)
                    queue.append((next_square, moves + 1))

        return -1
```

## Code Explanation

The board size and final square are:

```python
n = len(board)
target = n * n
```

The helper function converts a square label into matrix coordinates:

```python
def get_cell(square: int) -> tuple[int, int]:
```

We first convert to zero-based numbering:

```python
q = square - 1
```

Then compute which row it belongs to from the bottom:

```python
row_from_bottom = q // n
```

The actual matrix row is reversed because matrix row `0` is at the top:

```python
row = n - 1 - row_from_bottom
```

The column depends on the direction of that row:

```python
if row_from_bottom % 2 == 0:
    col = col_in_row
else:
    col = n - 1 - col_in_row
```

The BFS starts at square `1` with zero dice rolls:

```python
queue = deque([(1, 0)])
visited = {1}
```

For each square, try all six dice outcomes:

```python
for step in range(1, 7):
```

If the square has a snake or ladder, apply it once:

```python
if board[row][col] != -1:
    next_square = board[row][col]
```

Unvisited destinations are added to the queue with one more move:

```python
queue.append((next_square, moves + 1))
```

## Testing

```python
def run_tests():
    s = Solution()

    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],
    ]
    assert s.snakesAndLadders(board) == 4

    board = [
        [-1, -1],
        [-1, 3],
    ]
    assert s.snakesAndLadders(board) == 1

    board = [
        [-1, -1],
        [-1, -1],
    ]
    assert s.snakesAndLadders(board) == 1

    board = [
        [-1, -1, -1],
        [-1, 9, 8],
        [-1, 8, 9],
    ]
    assert s.snakesAndLadders(board) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `6 x 6` sample | Main BFS behavior |
| `2 x 2` with ladder | Checks one snake or ladder per move |
| `2 x 2` empty board | Goal reachable in one roll |
| Board with immediate ladder | Checks destination remapping |