# Snakes and Ladders
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/snakes-and-ladders)
Canonical: https://scaleengineer.com/dsa/problems/snakes-and-ladders
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [PhonePe](https://scaleengineer.com/companies/phonepe), [Zomato](https://scaleengineer.com/companies/zomato), [Pinterest](https://scaleengineer.com/companies/pinterest), [Anduril](https://scaleengineer.com/companies/anduril), [National Instruments](https://scaleengineer.com/companies/national-instruments), [thoughtspot](https://scaleengineer.com/companies/thoughtspot)
---
## Problem
You are given an `n x n` integer matrix `board` where the cells are labeled from `1` to `n2` in a [**Boustrophedon style**](https://en.wikipedia.org/wiki/Boustrophedon) starting from the bottom left of the board (i.e. `board[n - 1][0]`) and alternating direction each row.

You start on square `1` of the board. In each move, starting from square `curr`, do the following:

* Choose a destination square `next` with a label in the range `[curr + 1, min(curr + 6, n2)]`.  
  * This choice simulates the result of a standard **6-sided die roll**: i.e., there are always at most 6 destinations, regardless of the size of the board.
* If `next` has a snake or ladder, you **must** move to the destination of that snake or ladder. Otherwise, you move to `next`.
* The game ends when you reach the square `n2`.

A board square on row `r` and column `c` has a snake or ladder if `board[r][c] != -1`. The destination of that snake or ladder is `board[r][c]`. Squares `1` and `n2` are not the starting points of any snake or ladder.

Note that you only take a snake or ladder at most once per dice roll. If the destination to a snake or ladder is the start of another snake or ladder, you do **not** follow the subsequent snake or ladder.

* For example, suppose the board is `[[-1,4],[-1,3]]`, and on the first move, your destination square is `2`. You follow the ladder to square `3`, but do **not** follow the subsequent ladder to `4`.

Return _the least number of dice rolls required to reach the square_ `n2`_. If it is not possible to reach the square, return_ `-1`.

**Example 1:**

![](https://assets.glich.co/dsa/snakes-and-ladders/image0.png) 

**Input:** 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]]
**Output:** 4
**Explanation:** 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.

**Example 2:**

**Input:** board = [[-1,-1],[-1,3]]
**Output:** 1

**Constraints:**

* `n == board.length == board[i].length`
* `2 <= n <= 20`
* `board[i][j]` is either `-1` or in the range `[1, n2]`.
* The squares labeled `1` and `n2` are not the starting points of any snake or ladder.

# Approaches
## Brute-Force Depth-First Search (DFS)
This approach explores the game by trying every possible sequence of dice rolls recursively. It's a brute-force method that attempts to find a path to the destination square `n*n`. To find the *shortest* path, it must explore all possible paths from the start to the end and keep track of the minimum number of moves found so far. This is fundamentally inefficient because it doesn't prioritize shorter paths and explores many dead-ends and suboptimal routes.
**Time:** O(6^D), where D is the length of the longest simple path. In the worst case, this is exponential in N^2, making it infeasible for all but the smallest boards. · **Space:** O(N^2) for the recursion stack depth in the worst case, where N is the side length of the board. The `visitedOnPath` array also takes O(N^2) space.
**Pros:** Conceptually simple to understand as it mimics trying out all possibilities.
**Cons:** Extremely inefficient and will likely result in a "Time Limit Exceeded" error for most inputs.; Does not find the shortest path first; it must explore a potentially large number of paths to guarantee the minimum.; The state space can be very large, leading to deep recursion and potential stack overflow errors on large boards.
### Explanation
We define a recursive function, say `dfs(currentSquare, currentMoves)`, that explores paths from the `currentSquare`. The base case for the recursion is when `currentSquare` reaches `n*n`, at which point we compare `currentMoves` with a global minimum and update it if the current path is shorter. To prevent infinite loops (e.g., a snake leading back to a square we've already been on in the current path), we need to keep track of the squares visited along the current recursive path.

The function iterates through all possible next moves (dice rolls 1 to 6). For each move, it calculates the destination square, accounting for any snakes or ladders. It then makes a recursive call for the new square with an incremented move count. This approach is very inefficient because it explores paths in a depth-first manner, meaning it might explore a very long path completely before exploring a much shorter one. It essentially performs an exhaustive search of the state space, which is exponential in nature.

```java
class Solution {
    int minMoves = Integer.MAX_VALUE;
    int n;

    public int snakesAndLadders(int[][] board) {
        this.n = board.length;
        // Using a boolean array for the visited path for simplicity
        dfs(1, 0, new boolean[n * n + 1], board);
        return minMoves == Integer.MAX_VALUE ? -1 : minMoves;
    }

    private void dfs(int currentSquare, int moves, boolean[] visitedOnPath, int[][] board) {
        // Pruning: if we've already taken more moves than the best solution found so far
        if (moves >= minMoves) {
            return;
        }

        // Mark the current square as visited for this path
        visitedOnPath[currentSquare] = true;

        for (int i = 1; i <= 6; i++) {
            int nextSquare = currentSquare + i;
            if (nextSquare > n * n) {
                break;
            }

            int[] coords = getCoordinates(nextSquare);
            int r = coords[0];
            int c = coords[1];

            int finalDestination = board[r][c] == -1 ? nextSquare : board[r][c];

            if (finalDestination == n * n) {
                minMoves = Math.min(minMoves, moves + 1);
                // We can continue checking other dice rolls, as a shorter path might exist
                // from the current square, though this is unlikely with this problem's structure.
                continue;
            }

            if (!visitedOnPath[finalDestination]) {
                dfs(finalDestination, moves + 1, visitedOnPath, board);
            }
        }
        
        // Backtrack: un-mark the square so other paths can use it
        visitedOnPath[currentSquare] = false;
    }

    private int[] getCoordinates(int square) {
        int r = n - 1 - (square - 1) / n;
        int c = (square - 1) % n;
        if ((n - 1 - r) % 2 == 1) { // Odd row from top (0-indexed)
            c = n - 1 - c;
        }
        return new int[]{r, c};
    }
}
```
### Algorithm
*   Initialize a global variable `min_moves` to infinity.
*   Create a helper function `getCoordinates(square)` to convert a square number to its `(row, col)` coordinates.
*   Define a recursive function `dfs(square, moves, visited_path)`.
*   Inside `dfs`:
    *   If the current number of `moves` is already greater than or equal to `min_moves`, we can prune this path and return, as it won't be a better solution.
    *   If `square` is the target `n*n`, we have found a path. We update `min_moves = min(min_moves, moves)` and return.
    *   Mark the current `square` as visited in the current path to avoid cycles within a single path exploration.
    *   Iterate through each possible dice roll `d` from 1 to 6:
        *   Calculate `next_square = square + d`.
        *   If `next_square` exceeds `n*n`, stop exploring further dice rolls from this square.
        *   Use the helper function to get the coordinates for `next_square`.
        *   Check the board for a snake or ladder to determine the `final_dest`.
        *   If `final_dest` has not been visited in the current path, make a recursive call: `dfs(final_dest, moves + 1, visited_path)`.
    *   Unmark `square` from `visited_path` to allow other paths to visit this square (this is called backtracking).
*   Start the search by calling `dfs(1, 0, new HashSet<>())`.
*   After the search completes, if `min_moves` is still infinity, it means the destination was unreachable, so return -1. Otherwise, return `min_moves`.

## Breadth-First Search (BFS)
This problem can be modeled as finding the shortest path in an unweighted graph. Each square on the board is a node, and a move (a dice roll followed by a potential snake or ladder) represents an edge. Breadth-First Search (BFS) is the ideal algorithm for this scenario because it explores the graph layer by layer. This guarantees that the first time we reach the destination square `n*n`, it will be via the path with the minimum number of moves.
**Time:** O(N^2), where N is the side length of the board. Each square (node) from 1 to N^2 is enqueued and dequeued at most once. From each square, we perform a constant number of operations (at most 6) to find its neighbors. Therefore, the complexity is proportional to the number of squares. · **Space:** O(N^2), where N is the side length of the board. The `visited` array requires O(N^2) space. The queue, in the worst case, can also hold up to O(N^2) elements.
**Pros:** Guaranteed to find the shortest path in terms of the number of moves for an unweighted graph.; Highly efficient and the optimal approach for this problem.; Cleanly avoids infinite cycles and redundant computations using a `visited` set.
**Cons:** Requires extra space for the queue and the `visited` array, which can be up to O(N^2).
### Explanation
We start at square 1, which is at level 0 of our search. All squares reachable in one move are at level 1, all squares reachable from level 1 squares in one move are at level 2, and so on. BFS systematically explores these levels using a queue.

We use a queue to keep track of the squares to visit next and a `visited` array to ensure we don't process the same square multiple times, which prevents infinite loops and redundant computations. The search proceeds level by level. In each step, we dequeue all nodes from the current level, find all their unvisited neighbors (squares reachable in one move), and enqueue them. We increment our move counter after each level is fully processed. Because we explore all paths of length `k` before exploring any path of length `k+1`, the first time we encounter the target square, we are guaranteed to have done so in the minimum possible number of moves.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        boolean[] visited = new boolean[n * n + 1];
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(1);
        visited[1] = true;
        int moves = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int currentSquare = queue.poll();

                if (currentSquare == n * n) {
                    return moves;
                }

                for (int j = 1; j <= 6; j++) {
                    int nextSquare = currentSquare + j;
                    if (nextSquare > n * n) {
                        break;
                    }

                    int[] coords = getCoordinates(nextSquare, n);
                    int r = coords[0];
                    int c = coords[1];

                    int finalDestination = board[r][c] == -1 ? nextSquare : board[r][c];

                    if (!visited[finalDestination]) {
                        visited[finalDestination] = true;
                        queue.offer(finalDestination);
                    }
                }
            }
            moves++;
        }

        return -1; // Destination not reachable
    }

    private int[] getCoordinates(int square, int n) {
        // Convert 1-based square to 0-based index for calculation
        int s = square - 1;
        
        // Row from top (0-indexed)
        int rowFromTop = s / n;
        // Board row (from bottom, 0-indexed)
        int r = n - 1 - rowFromTop;

        // Column (0-indexed)
        int c = s % n;
        // Adjust column for Boustrophedon order
        if (rowFromTop % 2 == 1) { // If row from top is odd, direction is right-to-left
            c = n - 1 - c;
        }
        
        return new int[]{r, c};
    }
}
```
### Algorithm
*   Get the board size `n`.
*   Create a helper function `getCoordinates(square, n)` to convert a square number to its `(row, col)` coordinates.
*   Initialize a queue `q` of integers and add the starting square `1`.
*   Initialize a boolean array `visited` of size `n*n + 1` and set `visited[1] = true` to avoid cycles and redundant processing.
*   Initialize a variable `moves = 0`.
*   While the queue `q` is not empty:
    *   Get the number of nodes at the current level: `levelSize = q.size()`.
    *   Loop `levelSize` times to process all nodes at the current level before moving to the next.
        *   Dequeue the current square: `curr = q.poll()`.
        *   If `curr` is the target square `n*n`, we have found the shortest path. Return `moves`.
        *   For each possible dice roll `d` from 1 to 6:
            *   Calculate the potential next square: `next = curr + d`.
            *   If `next > n*n`, break the inner loop as further rolls will also be out of bounds.
            *   Get the board coordinates for `next`: `(r, c) = getCoordinates(next, n)`.
            *   Determine the final destination after checking for a snake or ladder: `dest = board[r][c] == -1 ? next : board[r][c]`.
            *   If `dest` has not been visited (`visited[dest]` is false):
                *   Mark it as visited: `visited[dest] = true`.
                *   Enqueue `dest` for processing in the next level: `q.add(dest)`.
    *   After processing the entire level, increment `moves`.
*   If the loop finishes (queue becomes empty) and we haven't reached the destination, it's unreachable. Return -1.

# Solutions
### Java

```java
class Solution {
private
  int n;
public
  int snakesAndLadders(int[][] board) {
    n = board.length;
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(1);
    boolean[] vis = new boolean[n * n + 1];
    vis[1] = true;
    int ans = 0;
    while (!q.isEmpty()) {
      for (int t = q.size(); t > 0; --t) {
        int curr = q.poll();
        if (curr == n * n) {
          return ans;
        }
        for (int k = curr + 1; k <= Math.min(curr + 6, n * n); ++k) {
          int[] p = get(k);
          int next = k;
          int i = p[0], j = p[1];
          if (board[i][j] != -1) {
            next = board[i][j];
          }
          if (!vis[next]) {
            vis[next] = true;
            q.offer(next);
          }
        }
      }
      ++ans;
    }
    return -1;
  }
private
  int[] get(int x) {
    int i = (x - 1) / n, j = (x - 1) % n;
    if (i % 2 == 1) {
      j = n - 1 - j;
    }
    return new int[]{n - 1 - i, j};
  }
}

```

### CPP

```cpp
class Solution {
public:
  int n;
  int snakesAndLadders(vector<vector<int>> &board) {
    n = board.size();
    queue<int> q{{1}};
    vector<bool> vis(n * n + 1);
    vis[1] = true;
    int ans = 0;
    while (!q.empty()) {
      for (int t = q.size(); t; --t) {
        int curr = q.front();
        if (curr == n * n)
          return ans;
        q.pop();
        for (int k = curr + 1; k <= min(curr + 6, n * n); ++k) {
          auto p = get(k);
          int next = k;
          int i = p[0], j = p[1];
          if (board[i][j] != -1)
            next = board[i][j];
          if (!vis[next]) {
            vis[next] = true;
            q.push(next);
          }
        }
      }
      ++ans;
    }
    return -1;
  }
  vector<int> get(int x) {
    int i = (x - 1) / n, j = (x - 1) % n;
    if (i % 2 == 1)
      j = n - 1 - j;
    return {n - 1 - i, j};
  }
};

```

### Python

```python
class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int: def get(x): i, j = (x - 1) // n, (x - 1) % n if i & 1: j = n - 1 - j return n - 1 - i, j n = len(board) q = deque([1]) vis = {1} ans = 0 while q: for _ in range(len(q)): curr = q . popleft() if curr == n * n: return ans for next in range(curr + 1, min(curr + 7, n * n + 1)): i, j = get(next) if board[i][j] != - 1: next = board[i][j] if next not in vis: q . append(next) vis . add(next) ans += 1 return - 1

```