LeetCode Solutions

Time: $O(n^2)$

Space: $O(n^2)$

			

class Solution {
 public:
  int snakesAndLadders(vector<vector<int>>& board) {
    const int n = board.size();
    int ans = 0;
    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 & 1 ? j + 1 : n - j)] = board[i][j];

    while (!q.empty()) {
      ++ans;
      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 ans;
          if (seen[dest])
            continue;
          q.push(dest);
          seen[dest] = true;
        }
      }
    }

    return -1;
  }
};

			

class Solution {
  public int snakesAndLadders(int[][] board) {
    final int n = board.length;
    int ans = 0;
    Queue<Integer> q = new ArrayDeque<>(Arrays.asList(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 & 1) == 1 ? j + 1 : n - j)] = board[i][j];

    while (!q.isEmpty()) {
      ++ans;
      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 ans;
          if (seen[dest])
            continue;
          q.offer(dest);
          seen[dest] = true;
        }
      }
    }

    return -1;
  }
}

			

class Solution:
  def snakesAndLadders(self, board: List[List[int]]) -> int:
    n = len(board)
    ans = 0
    q = 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 + (j + 1 if n - i & 1 else n - j)] = board[i][j]

    while q:
      ans += 1
      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 ans
          if dest in seen:
            continue
          q.append(dest)
          seen.add(dest)

    return -1