Snakes and Ladders Medium 0 attempts
LeetCode ↗

Snakes and Ladders

Medium GraphBFSDFS LeetCode

You're given an n×n snakes-and-ladders board, numbered boustrophedon-style: squares run from 1 to n^2 starting at the bottom-left, moving right along the bottom row, then alternating direction on each row going up. Each square is either -1 (nothing special) or the destination of a snake or ladder. Starting from square 1 and rolling a standard die each turn, find the minimum number of dice rolls needed to reach the last square, following at most one snake or ladder per roll (do not chain jumps). Return -1 if the final square is unreachable.

Input Format
Implement snakesAndLadders(board). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
board = [[-1,-1],[-1,-1]]
Output
1

Example 2

Input
board = [[-1,-1,-1],[-1,-1,-1],[-1,-1,-1]]
Output
2
Constraints
  • n == board.length == board[i].length
  • 2 <= n <= 20
  • -1 <= board[i][j] <= n^2
Test Cases (2)
Case 1
Args: [[[-1,-1],[-1,-1]]] Expected: 1
Case 2
Args: [[[-1,-1,-1],[-1,-1,-1],[-1,-1,-1]]] Expected: 2
Topics
GraphBFSDFS

BFS

javascript
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]];
  let head = 0;
  while (head < q.length) {
    const [pos, moves] = q[head++];
    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