題目資訊

題目編號: 3341
題目連結: Find Minimum Time to Reach Last Room I
主題: Array, Graph, Heap (Priority Queue), Matrix, Shortest Path

題目敘述

有一個地牢包含 $n \times m$ 個房間，依照網格排列。

給你一個大小為 $n \times m$ 的二維陣列 moveTime，其中 moveTime[i][j] 表示可以開始移動到該房間的最小時間，以秒為單位。你在時間 $t = 0$ 從房間 (0, 0) 開始，可以移動到一個相鄰的房間。移動到相鄰的房間需要正好一秒。

返回到達房間 $(n - 1, m - 1)$ 的最小時間。

如果兩個房間共享一個公共牆壁，它們就是相鄰的房間，可以是水平或垂直。

範例 1:

輸入: moveTime = [[0,4],[4,4]]

輸出: 6

解釋:

所需的最小時間是 6 秒。

在時間 $t == 4$，從房間 (0, 0) 移動到房間 (1, 0)，耗時一秒。
在時間 $t == 5$，從房間 (1, 0) 移動到房間 (1, 1)，耗時一秒。

範例 2:

輸入: moveTime = [[0,0,0],[0,0,0]]

輸出: 3

解釋:

所需的最小時間是 3 秒。

在時間 $t == 0$，從房間 (0, 0) 移動到房間 (1, 0)，耗時一秒。
在時間 $t == 1$，從房間 (1, 0) 移動到房間 (1, 1)，耗時一秒。
在時間 $t == 2$，從房間 (1, 1) 移動到房間 (1, 2)，耗時一秒。

範例 3:

輸入: moveTime = [[0,1],[1,2]]

輸出: 3

限制條件:

$2 \leq n == \text{moveTime.length} \leq 50$
$2 \leq m == \text{moveTime[i].length} \leq 50$
$0 \leq \text{moveTime[i][j]} \leq 10^{9}$

直覺

該問題要求計算在網格佈局中到達特定房間的最短時間，每個單元格都有進入前的最小時間限制。這類似於一個具有特定時間限制的節點的路徑尋找問題。挑戰在於從左上角導航到右下角，同時遵守這些限制。自然的解決方案涉及探索網格，同時優化遍歷時間並遵循進入每個單元格的時間規則。

解法

我們可以使用優先佇列來實現類似Dijkstra的算法，這樣可以有效地處理時間限制，並使我們能夠優先選擇可能具有較低旅遊時間的路徑。以下是詳細的方法：

資料結構初始化：
初始化一個優先佇列（最小堆）以根據累計旅行時間以升序管理單元格，確保處理下一個時間最短的單元格。這允許最佳路徑探索。此外，創建一個二維布林數組以跟踪已訪問的單元格，防止冗餘處理和無限迴圈。
優先佇列設置：
首先將起始單元格 $(0, 0)$ 與初始時間 $0$ 一起添加到優先佇列。優先佇列將維護形式為 $(\text{current\_time}, (\text{row}, \text{column}))$ 的元組。
探索循環：
使用循環來處理單元格，直到佇列為空：
- 從優先佇列中提取時間最小的單元格。
- 如果這個單元格是目標 $(n-1, m-1)$，則返回其時間作為答案。
- 標記當前單元格為已訪問。
- 探索所有鄰近單元格（上、下、左、右）。對於每一個鄰居：
  - 驗證該單元格是否在網格範圍內且未被訪問。
  - 計算移動到此單元格所需的時間：這是當前單元格時間和此單元格開始移動時間的最大值，加上移動所需的1秒。
  - 將這些鄰居單元格以其計算出的移動時間插入優先佇列中。使用負值來實現一個最小堆，因為標準C++優先佇列默認為一個最大堆。
終止和邊界情況：
如果優先佇列用盡而未到達目的地，則返回 $-1$（表示目的地不可達，雖然在給定的問題限制下這種情況不太可能發生）。

通過堅持這種基於優先級的探索策略，我們確保我們始終以最低旅行時間擴展路徑，有效地管理約束並高效地解決問題。

程式碼

C++

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n = moveTime.size();  // 行數
        int m = moveTime[0].size();  // 列數
        vector<vector<bool>> visited(n, vector<bool>(m, false));  // 訪問過的房間追蹤器
        int moves[] = {1, 0, -1, 0, 1};  // 方向向量用於向上、右、下、左移動
        priority_queue<pair<int, pair<int, int>>> pq;  // 最小堆優先佇列

        // 從初始房間 (0, 0) 並以時間 0 開始
        pq.push({0, {0, 0}});

        while (!pq.empty()) {
            // 獲取當前房間及時間
            pair<int, pair<int, int>> cur_pair = pq.top();
            pq.pop();
            int cur_y = cur_pair.second.first;  // 當前行
            int cur_x = cur_pair.second.second;  // 當前列

            // 若已訪問過則跳過
            if (visited[cur_y][cur_x]) continue;

            // 標記當前房間為已訪問
            visited[cur_y][cur_x] = true;

            // 若已到達目標房間 (n-1, m-1)，返回時間
            if (cur_y == n - 1 && cur_x == m - 1) return -cur_pair.first;

            // 探索相鄰房間
            for (int i = 0; i < 4; i++) {
                int nxt_y = cur_y + moves[i];  // 下一行
                int nxt_x = cur_x + moves[i + 1];  // 下一列

                // 檢查下一個房間是否在邊界內
                if (nxt_y < 0 || nxt_y >= n || nxt_x < 0 || nxt_x >= m) continue;

                // 將下一個房間新增到優先佇列中並更新時間
                pq.push({-max(-cur_pair.first, moveTime[nxt_y][nxt_x]) - 1, {nxt_y, nxt_x}});
            }
        }

        return -1;  // 若目標房間無法到達，則返回 -1（在有效輸入情況下不太可能發生）
    }
};

Python

from heapq import heappush, heappop

class Solution:
    def minTimeToReach(self, moveTime):
        n = len(moveTime)  # 行的數量
        m = len(moveTime[0])  # 列的數量
        visited = [[False] * m for _ in range(n)]  # 記錄已訪問的房間
        moves = [1, 0, -1, 0, 1]  # 用於向上、右、下、左移動的方向向量
        pq = []  # 最小堆優先隊列

        # 從初始房間 (0, 0) 並在時間 0 開始
        heappush(pq, (0, 0, 0))

        while pq:
            # 取得當前房間和時間
            cur_time, cur_y, cur_x = heappop(pq)

            # 如果已經訪問過，就跳過
            if visited[cur_y][cur_x]:
                continue

            # 標記當前房間為已訪問
            visited[cur_y][cur_x] = True

            # 如果已經到達目標房間 (n-1, m-1)，返回所需時間
            if cur_y == n - 1 and cur_x == m - 1:
                return -cur_time

            # 探索相鄰房間
            for i in range(4):
                nxt_y = cur_y + moves[i]  # 下一行
                nxt_x = cur_x + moves[i + 1]  # 下一列

                # 檢查下一個房間是否在邊界內
                if nxt_y < 0 or nxt_y >= n or nxt_x < 0 or nxt_x >= m:
                    continue

                # 將下一個房間連同更新後的時間放入優先隊列
                heappush(pq, (-max(-cur_time, moveTime[nxt_y][nxt_x]) - 1, nxt_y, nxt_x))

        return -1  # 如果無法到達目標房間則返回-1（針對無效輸入的情況不太可能發生）

複雜度分析

時間複雜度: 時間複雜度大約為 $O(n \cdot m \cdot \log(n \cdot m))$。這是因為在最壞情況下，$n \times m$ 格子中的每個房間都將被處理一次，而在優先佇列（小頂堆）中的每次插入或提取操作都需要 $O(\log(n \cdot m))$。因此，總體複雜度大約被限制在 $O(n \cdot m \cdot \log(n \cdot m))$。
空間複雜度: 空間複雜度為 $O(n \cdot m)$，這計算了維護 visited 陣列和優先佇列所需的空間，在最壞情況下，這些空間最多可以存儲 $n \cdot m$ 個元素。

CS Note
En

Leetcode 3341. Find Minimum Time to Reach Last Room I

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析