Skip to content

909. Snakes and Ladders

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int snakesAndLadders(vector<vector<int>>& board) {
    const int n = board.size();
    queue<int> q{{1}};
    vector<bool> seen(1 + n * n);
    vector<int> A(1 + n * n);  // 2D -> 1D

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        A[(n - 1 - i) * n + ((n - i) % 2 == 0 ? n - j : j + 1)] = board[i][j];

    for (int step = 1; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        const int curr = q.front();
        q.pop();
        for (int next = curr + 1; next <= min(curr + 6, n * n); ++next) {
          const int dest = A[next] > 0 ? A[next] : next;
          if (dest == n * n)
            return step;
          if (seen[dest])
            continue;
          q.push(dest);
          seen[dest] = true;
        }
      }

    return -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int snakesAndLadders(int[][] board) {
    final int n = board.length;
    Queue<Integer> q = new ArrayDeque<>(List.of(1));
    boolean[] seen = new boolean[1 + n * n];
    int[] A = new int[1 + n * n]; // 2D -> 1D

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        A[(n - 1 - i) * n + ((n - i) % 2 == 0 ? n - j : j + 1)] = board[i][j];

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int curr = q.poll();
        for (int next = curr + 1; next <= Math.min(curr + 6, n * n); ++next) {
          final int dest = A[next] > 0 ? A[next] : next;
          if (dest == n * n)
            return step;
          if (seen[dest])
            continue;
          q.offer(dest);
          seen[dest] = true;
        }
      }

    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def snakesAndLadders(self, board: list[list[int]]) -> int:
    n = len(board)
    q = collections.deque([1])
    seen = set()
    A = [0] * (1 + n * n)  # 2D -> 1D

    for i in range(n):
      for j in range(n):
        A[(n - 1 - i) * n + (n - j if (n - i) % 2 == 0 else j + 1)] = board[i][j]

    step = 1
    while q:
      for _ in range(len(q)):
        curr = q.popleft()
        for next in range(curr + 1, min(curr + 6, n * n) + 1):
          dest = A[next] if A[next] > 0 else next
          if dest == n * n:
            return step
          if dest in seen:
            continue
          q.append(dest)
          seen.add(dest)
      step += 1

    return -1