Skip to content

3342. Find Minimum Time to Reach Last Room II 👍

  • 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
class Solution {
 public:
  // Similar to 3341. Find Minimum Time to Reach Last Room I
  int minTimeToReach(vector<vector<int>>& moveTime) {
    return dijkstra(moveTime, {0, 0},
                    {moveTime.size() - 1, moveTime[0].size() - 1});
  }

 private:
  int dijkstra(const vector<vector<int>>& moveTime, 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 = moveTime.size();
    const int n = moveTime[0].size();
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));

    dist[0][0] = 0;
    using T = pair<int, pair<int, int>>;  // (d, (ux, uy))
    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;
      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;
        const int newDist = max(moveTime[x][y], d) + ((i + j) % 2 + 1);
        if (newDist < dist[x][y]) {
          dist[x][y] = newDist;
          minHeap.push({newDist, {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
class Solution {
  // Similar to 3341. Find Minimum Time to Reach Last Room I
  public int minTimeToReach(int[][] moveTime) {
    return dijkstra(moveTime, new Pair<>(0, 0),
                    new Pair<>(moveTime.length - 1, moveTime[0].length - 1));
  }

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

    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, (ux, uy))
        };

    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;
      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;
        final int newDist = Math.max(moveTime[x][y], d) + ((i + j) % 2 + 1);
        if (newDist < dist[x][y]) {
          dist[x][y] = newDist;
          minHeap.offer(new Pair<>(newDist, 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
class Solution:
  # Similar to 3341. Find Minimum Time to Reach Last Room I
  def minTimeToReach(self, moveTime: list[list[int]]) -> int:
    return self._dijkstra(moveTime,
                          (0, 0),
                          (len(moveTime) - 1, len(moveTime[0]) - 1))

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

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

    while minHeap:
      d, u = heapq.heappop(minHeap)
      if u == dst:
        return d
      i, j = u
      if d > dist[i][j]:
        continue
      for dx, dy in DIRS:
        x = i + dx
        y = j + dy
        if x < 0 or x == m or y < 0 or y == n:
          continue
        newDist = max(moveTime[x][y], d) + (i + j) % 2 + 1
        if newDist < dist[x][y]:
          dist[x][y] = newDist
          heapq.heappush(minHeap, (newDist, (x, y)))

    return -1