Skip to content

3552. Grid Teleportation Traversal 👍

  • Time: $O(mn\log mn)$
  • Space: $O(mn)$
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
 public:
  // Similar to 3341. Find Minimum Time to Reach Last Room I
  int minMoves(vector<string>& matrix) {
    if (matrix.back().back() == '#')
      return -1;

    vector<vector<pair<int, int>>> teleportPositions(26);

    for (int i = 0; i < matrix.size(); ++i)
      for (int j = 0; j < matrix[0].size(); ++j)
        if (matrix[i][j] != '.' && matrix[i][j] != '#')
          teleportPositions[matrix[i][j] - 'A'].emplace_back(i, j);

    return dijkstra(matrix, teleportPositions, {0, 0},
                    {matrix.size() - 1, matrix[0].size() - 1});
  }

 private:
  int dijkstra(const vector<string>& matrix,
               const vector<vector<pair<int, int>>>& teleportPositions,
               const pair<int, int>& src, const pair<int, int>& dst) {
    constexpr int kDirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = matrix.size();
    const int n = matrix[0].size();
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
    vector<bool> seen(26);

    dist[0][0] = 0;
    using T = pair<int, pair<int, int>>;  // (d, u)
    priority_queue<T, vector<T>, greater<>> minHeap;
    minHeap.push({dist[0][0], src});

    while (!minHeap.empty()) {
      const auto [d, u] = minHeap.top();
      minHeap.pop();
      if (u == dst)
        return d;
      const auto [i, j] = u;
      if (d > dist[i][j])
        continue;
      const char c = matrix[i][j];
      if (isupper(c) && !seen[c - 'A']) {
        seen[c - 'A'] = true;
        for (const auto& [x, y] : teleportPositions[c - 'A'])
          if (d < dist[x][y]) {
            dist[x][y] = d;
            minHeap.push({d, {x, y}});
          }
      }
      for (const auto& [dx, dy] : kDirs) {
        const int x = i + dx;
        const int y = j + dy;
        if (x < 0 || x == m || y < 0 || y == n)
          continue;
        if (matrix[x][y] == '#')
          continue;
        if (d + 1 < dist[x][y]) {
          dist[x][y] = d + 1;
          minHeap.push({d + 1, {x, y}});
        }
      }
    }

    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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
  // Similar to 3341. Find Minimum Time to Reach Last Room I
  public int minMoves(String[] matrix) {
    if (matrix[matrix.length - 1].charAt(matrix[0].length() - 1) == '#')
      return -1;

    List<Pair<Integer, Integer>>[] teleportPositions = new ArrayList[26];

    for (int i = 0; i < 26; ++i)
      teleportPositions[i] = new ArrayList<>();

    for (int i = 0; i < matrix.length; ++i)
      for (int j = 0; j < matrix[0].length(); ++j) {
        final char c = matrix[i].charAt(j);
        if (c != '.' && c != '#')
          teleportPositions[c - 'A'].add(new Pair<>(i, j));
      }

    return dijkstra(matrix, teleportPositions, new Pair<>(0, 0),
                    new Pair<>(matrix.length - 1, matrix[0].length() - 1));
  }

  private int dijkstra(String[] matrix, List<Pair<Integer, Integer>>[] teleportPositions,
                       Pair<Integer, Integer> src, Pair<Integer, Integer> dst) {
    final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int m = matrix.length;
    final int n = matrix[0].length();
    int[][] dist = new int[m][n];
    Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    boolean[] seen = new boolean[26];

    dist[0][0] = 0;
    Queue<Pair<Integer, Pair<Integer, Integer>>> minHeap =
        new PriorityQueue<>(Comparator.comparingInt(Pair::getKey)) {
          { offer(new Pair<>(dist[0][0], src)); } // (d, u)
        };

    while (!minHeap.isEmpty()) {
      final int d = minHeap.peek().getKey();
      final Pair<Integer, Integer> u = minHeap.poll().getValue();
      if (u.equals(dst))
        return d;
      final int i = u.getKey();
      final int j = u.getValue();
      if (d > dist[i][j])
        continue;
      final char c = matrix[i].charAt(j);
      if (Character.isUpperCase(c) && !seen[c - 'A']) {
        seen[c - 'A'] = true;
        for (Pair<Integer, Integer> pos : teleportPositions[c - 'A']) {
          final int x = pos.getKey();
          final int y = pos.getValue();
          if (d < dist[x][y]) {
            dist[x][y] = d;
            minHeap.offer(new Pair<>(d, new Pair<>(x, y)));
          }
        }
      }
      for (int[] dir : DIRS) {
        final int x = i + dir[0];
        final int y = j + dir[1];
        if (x < 0 || x == m || y < 0 || y == n)
          continue;
        if (matrix[x].charAt(y) == '#')
          continue;
        if (d + 1 < dist[x][y]) {
          dist[x][y] = d + 1;
          minHeap.offer(new Pair<>(d + 1, new Pair<>(x, y)));
        }
      }
    }

    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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution:
  # Similar to 3341. Find Minimum Time to Reach Last Room I
  def minMoves(self, matrix: list[str]) -> int:
    if matrix[-1][-1] == '#':
      return -1

    teleportPositions = [[] for _ in range(26)]

    for i, row in enumerate(matrix):
      for j, c in enumerate(row):
        if c not in ('.', '#'):
          teleportPositions[ord(c) - ord('A')].append((i, j))

    return self._dijkstra(matrix, teleportPositions,
                          (0, 0), (len(matrix) - 1, len(matrix[0]) - 1))

  def _dijkstra(
      self,
      matrix: list[str],
      teleportPositions: list[list[tuple[int, int]]],
      src: tuple[int, int],
      dst: tuple[int, int],
  ) -> int:
    DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    m = len(matrix)
    n = len(matrix[0])
    dist = [[math.inf] * n for _ in range(m)]
    seen = set()

    dist[0][0] = 0
    minHeap = [(dist[0][0], src)]  # (d, u)

    while minHeap:
      d, u = heapq.heappop(minHeap)
      if u == dst:
        return d
      i, j = u
      if d > dist[i][j]:
        continue
      c = matrix[i][j]
      if c.isupper() and c not in seen:
        seen.add(c)
        for x, y in teleportPositions[ord(c) - ord('A')]:
          if d < dist[x][y]:
            dist[x][y] = d
            heapq.heappush(minHeap, (d, (x, y)))
      for dx, dy in DIRS:
        x = i + dx
        y = j + dy
        if x < 0 or x == m or y < 0 or y == n:
          continue
        if matrix[x][y] == '#':
          continue
        if d + 1 < dist[x][y]:
          dist[x][y] = d + 1
          heapq.heappush(minHeap, (d + 1, (x, y)))

    return -1