Snakes and Ladders Medium 0 attempts
LeetCode ↗

Snakes and Ladders

Medium GraphBFSDFS LeetCode

Given an n×n board for snakes and ladders, find the minimum dice rolls to reach the last square from square 1.

Example: board (with snakes/ladders) → minimum moves

Sample Input
—
Sample Output
—
Constraints
  • n == board.length == board[i].length
  • 2 <= n <= 20
  • -1 <= board[i][j] <= n^2
Topics
GraphBFSDFS

BFS

function snakesAndLadders(board) {
  const n = board.length;
  function getRC(s) {
    const r = Math.floor((s-1)/n), c = (s-1)%n;
    return [n-1-r, r%2===0 ? c : n-1-c];
  }
  const visited = new Set([1]), q = [[1, 0]];
  while (q.length) {
    const [pos, moves] = q.shift();
    for (let i = 1; i <= 6; i++) {
      let next = pos + i; if (next > n*n) continue;
      const [r, c] = getRC(next);
      if (board[r][c] !== -1) next = board[r][c];
      if (next === n*n) return moves + 1;
      if (!visited.has(next)) { visited.add(next); q.push([next, moves+1]); }
    }
  }
  return -1;
}

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

Saved in this browser only. Private to you.

JavaScript