Snakes and Ladders

medium graph bfs shortest path

Problem

On an N x N board, the numbers from 1 to N*N are written boustrophedonically starting from the bottom left of the board, and alternating direction each row. For example, for a 6 x 6 board, the numbers are written as follows: You start on square 1 of the board (which is always in the last row and first column). Each move, starting from square x, consists of the following: You choose a destination square S with number x+1, x+2, x+3, x+4, x+5, or x+6, provided this number is <= N*N. (This choice simulates the result of a standard 6-sided die roll: ie., there are always at most 6 destinations, regardless of the size of the board.) If S has a snake or ladder, you move to the destination of that snake or ladder.

Squares are nodes; from each square 6 outgoing edges (one per face) lead to the post-teleport square. Standard BFS from square 1 gives the layered shortest path in number of rolls.

Inputn = 4, jumps = "5→14, 11→2"

Output2

Roll a 4 from 1 → 5 → ladder up to 14 (1 roll). Then roll a 2 → 16 (2 rolls).

jumps (e.g. "5,14; 11,2")

from collections import deque
def snakes_and_ladders(n, jump):
    end = n * n
    seen = {1}; q = deque([(1, 0)])
    while q:
        s, r = q.popleft()
        if s == end: return r
        for d in range(1, 7):
            t = s + d
            if t > end: break
            t = jump.get(t, t)
            if t not in seen:
                seen.add(t); q.append((t, r + 1))
    return -1

function snakesAndLadders(n, jump) {
  const end = n * n;
  const seen = new Set([1]);
  const q = [[1, 0]];
  while (q.length) {
    const [s, r] = q.shift();
    if (s === end) return r;
    for (let d = 1; d <= 6; d++) {
      let t = s + d;
      if (t > end) break;
      if (jump.has(t)) t = jump.get(t);
      if (!seen.has(t)) { seen.add(t); q.push([t, r + 1]); }
    }
  }
  return -1;
}

int snakesAndLadders(int n, Map<Integer,Integer> jump) {
    int end = n * n;
    boolean[] seen = new boolean[end + 1];
    Deque<int[]> q = new ArrayDeque<>();
    q.add(new int[]{1, 0}); seen[1] = true;
    while (!q.isEmpty()) {
        int[] cur = q.poll(); int s = cur[0], r = cur[1];
        if (s == end) return r;
        for (int d = 1; d <= 6; d++) {
            int t = s + d;
            if (t > end) break;
            if (jump.containsKey(t)) t = jump.get(t);
            if (!seen[t]) { seen[t] = true; q.add(new int[]{t, r + 1}); }
        }
    }
    return -1;
}

int snakesAndLadders(int n, unordered_map<int,int>& jump) {
    int end = n * n;
    vector<bool> seen(end + 1, false);
    queue<pair<int,int>> q; q.push({1, 0}); seen[1] = true;
    while (!q.empty()) {
        auto [s, r] = q.front(); q.pop();
        if (s == end) return r;
        for (int d = 1; d <= 6; d++) {
            int t = s + d;
            if (t > end) break;
            auto it = jump.find(t); if (it != jump.end()) t = it->second;
            if (!seen[t]) { seen[t] = true; q.push({t, r + 1}); }
        }
    }
    return -1;
}

Explanation

We want the fewest dice rolls to reach the last square. Each square is a node, and from any square you can move to the next 6 squares (one per die face), so this is a shortest path on an unweighted graph, which means BFS is the right tool.

BFS explores the board in waves: all squares reachable in 1 roll, then 2 rolls, and so on. The first time we pop the final square end = n*n, the roll count attached to it is guaranteed to be the minimum.

From a square s, we try each die value d from 1 to 6, landing on t = s + d. If that square has a snake or ladder, we jump to its destination via jump.get(t, t). A seen set prevents revisiting squares so we never loop.

Each queue entry stores (square, rolls). Newly discovered squares get rolls + 1. If the queue empties without reaching the end, the board is unsolvable and we return -1.

Example: n = 4 with a ladder 5→14. From square 1 a roll of 4 lands on 5, the ladder lifts you to 14 (1 roll). A roll of 2 then reaches 16, the last square, in 2 rolls.

Time: O(n²) Space: O(n²)