MediumRating 1862
3342. Find Minimum Time to Reach Last Room II
arraygraphheap-priority-queuematrixshortest-path
解題說明
Find Minimum Time to Reach Last Room II
題目描述：與 Part I 類似，但移動花費交替為 1 秒和 2 秒。第一次移動花 1 秒，第二次花 2 秒，第三次花 1 秒，以此類推。求從 (0, 0) 到 (m-1, n-1) 的最小時間。
解題思路：在 Dijkstra 的基礎上增加一個狀態維度：當前是第奇數次移動（花 1 秒）還是第偶數次移動（花 2 秒）。狀態為 (time, row, col, parity)，其中 parity 為 0 表示下次移動花 1 秒，1 表示下次移動花 2 秒。轉移時到達鄰居的時間為 max(dist, moveTime[nx][ny]) + (parity == 0 ? 1 : 2)，且 parity 翻轉。
C++ 解法
複雜度分析
時間複雜度：O(m × n × log(m × n)) — 狀態數為 O(m × n × 2)，每個狀態最多入堆一次。
空間複雜度：O(m × n) — 距離矩陣（每格兩個奇偶狀態）和優先佇列。
虛擬碼
1. Initialize dist[0][0][0] = 0 (parity 0 = next move costs 1)
2. Push (0, 0, 0, parity=0) to min-heap
3. While heap is not empty:
a. Pop (d, x, y, p); if destination, return d
b. Skip if d > dist[x][y][p]
c. moveCost = 1 if p==0, else 2; next_parity = 1-p
d. For each neighbor (nx, ny):
new_time = max(d, moveTime[nx][ny]) + moveCost
If new_time < dist[nx][ny][next_parity]: update and push
4. Return -1其他解法
忽略奇偶性的 Dijkstra（Part I 解法）：如果不考慮交替花費，直接用 Part I 解法。但本題要求交替，所以必須增加 parity 狀態。
A 搜尋*：使用曼哈頓距離作為啟發式函數加速 Dijkstra。在網格圖上效果良好，但最壞情況複雜度不變。
延伸思考
- 如果移動花費的週期不是 2（交替 1, 2）而是 k（例如 1, 2, 3, 1, 2, 3, ...），狀態空間如何擴展？
- 如果不同方向的移動花費不同（例如向上 3 秒，向右 1 秒），如何建模？
- 如果起點和終點可以是任意位置，如何計算所有點對的最短時間？