MediumRating 1721

3341. Find Minimum Time to Reach Last Room I

arraygraphheap-priority-queuematrixshortest-path

解題說明

Find Minimum Time to Reach Last Room I

題目描述：給定一個 m×n 的矩陣 moveTime，其中 moveTime[i][j] 表示你最早可以開始移動到房間 (i, j) 的時間。每次移動到相鄰房間需花費 1 秒。求從 (0, 0) 到達 (m-1, n-1) 的最小時間。

解題思路：這是一個帶有等待條件的最短路問題。使用 Dijkstra 演算法。到達 (i, j) 的最短時間為 dist[i][j]。當從 (i, j) 移動到鄰居 (ni, nj) 時，你必須等到 moveTime[ni][nj] 才能開始移動，移動本身花費 1 秒。因此到達鄰居的時間為 max(dist[i][j], moveTime[ni][nj]) + 1。

C++ 解法

複雜度分析

時間複雜度：O(m × n × log(m × n)) — Dijkstra 最多處理 m×n 個節點，每次堆操作 O(log(m×n))。

空間複雜度：O(m × n) — 距離矩陣和優先佇列。

虛擬碼

1. Initialize dist[0][0] = 0, all others = INF
2. Push (0, 0, 0) to min-heap
3. While heap is not empty:
   a. Pop (d, x, y); if destination reached, return d
   b. Skip if d > dist[x][y]
   c. For each neighbor (nx, ny):
      new_time = max(d, moveTime[nx][ny]) + 1
      If new_time < dist[nx][ny]: update and push
4. Return -1 (unreachable)

其他解法

BFS + 二分答案 O(m × n × log T)：二分最終答案時間 T，BFS 驗證是否能在 T 秒內到達。時間複雜度不優於 Dijkstra，且實作更複雜。

動態規劃（僅向右/向下） O(m × n)：若限制只能向右或向下移動，可用 DP 求解。但此題允許四方向移動，需用最短路演算法。

延伸思考

如果移動的花費不是固定 1 秒而是取決於方向（例如向上走 2 秒），如何修改？（參見 Part II）
如果有些房間完全不可通行，如何處理？
如果要求經過特定中繼點再到達終點，問題如何建模？

Find Minimum Time to Reach Last Room I — CaffeCode