Leetcode - 909. Snakes and Ladders

#leetcode

Approach

We treat the Snakes and Ladders board as an unweighted graph:

Each square = a node.
From a square s, you can move to s+1 through s+6 (dice roll).
If the landing square has a ladder or snake (board[r][c] != -1), you immediately jump to its target.
Goal: reach square n² with the minimum throws.

Why BFS?

BFS explores level-by-level (move count).
The first time we reach n² is guaranteed to be the shortest path.

Steps:

Map square number → (row, col) considering the zigzag pattern.
Start BFS from square 1 with moves = 0.
For each square, try dice rolls from 1 to 6:

Apply snake/ladder if present.
If the target is n², return moves + 1.
1. Keep track of visited squares to avoid loops.

Board Numbering (6×6)

After mapping zigzag pattern:

36 35 34 33 32 31
25 26 27 28 29 30
24 23 22 21 20 19
13 14 15 16 17 18
12 11 10  9  8  7
 1  2  3  4  5  6

BFS Expansion Example (Simplified)

Let’s assume:

Ladder at 3 → 22
Snake at 27 → 1

BFS layers (queue in [square, moves]):

Level 0:
[1, 0]

From 1, dice rolls:

2
3 → 22 (ladder)
4
5
6
7

Queue after level 0:
[2,1] [22,1] [4,1] [5,1] [6,1] [7,1]

Level 1:
From 22:

Roll 1 → 23
Roll 2 → 24
Roll 3 → 25
Roll 4 → 26
Roll 5 → 27 → 1 (snake) [already visited, skip]
Roll 6 → 28

From 28 or others, BFS keeps exploring… until it hits 36, returning the minimum moves.

Code

/**
 * @param {number[][]} board
 * @return {number}
 */
var snakesAndLadders = function(board) {
  const n = board.length;
  const N = n * n;

  function intToPos(square) {
    const rFromBottom = Math.floor((square - 1) / n);
    const row = n - 1 - rFromBottom;
    const colInRow = (square - 1) % n;
    return rFromBottom % 2 === 0
      ? [row, colInRow]
      : [row, n - 1 - colInRow];
  }

  const visited = new Array(N + 1).fill(false);
  const queue = [[1, 0]];
  visited[1] = true;

  while (queue.length) {
    const [square, moves] = queue.shift();

    for (let d = 1; d <= 6; d++) {
      let next = square + d;
      if (next > N) continue;

      const [r, c] = intToPos(next);
      if (board[r][c] !== -1) next = board[r][c];

      if (next === N) return moves + 1;

      if (!visited[next]) {
        visited[next] = true;
        queue.push([next, moves + 1]);
      }
    }
  }
  return -1;
};