Fewest Rolls to Reach the End in Snakes and Ladders

medium graph bfs shortest path

Problem

An n×n board is numbered in boustrophedon (zig-zag) order from 1 (bottom-left) to n*n. From square s you may roll the die and move to any of the next 6 squares, then if a snake or ladder lives there you teleport to its destination. Return the minimum rolls to land on n*n, or -1 if unreachable.

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 min_rolls(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 minRolls(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 minRolls(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 minRolls(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;
}

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