題目資訊

題目編號: 3342
題目連結: Find Minimum Time to Reach Last Room II
主題: 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]]

輸出: 7

解釋:

所需的最小時間是 7 秒。

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

例子 2:

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

輸出: 6

解釋:

所需的最小時間是 6 秒。

在時間 $t == 0$ 時，從房間 $(0, 0)$ 移動到房間 $(1, 0)$，花費一秒。
在時間 $t == 1$ 時，從房間 $(1, 0)$ 移動到房間 $(1, 1)$，花費兩秒。
在時間 $t == 3$ 時，從房間 $(1, 1)$ 移動到房間 $(1, 2)$，花費一秒。
在時間 $t == 4$ 時，從房間 $(1, 2)$ 移動到房間 $(1, 3)$，花費兩秒。

例子 3:

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

輸出: 4

約束條件:

$2 \leq n == moveTime.length \leq 750$
$2 \leq m == moveTime[i].length \leq 750$
$0 \leq moveTime[i][j] \leq 10^9$

直覺

此問題要求我們計算從網格的左上角到右下角的最短時間，這個網格中每一個單元格都有進入的時間限制，並且在相鄰單元格之間的移動時間交替為一秒或兩秒。這個問題可以被視為一個圖遍歷問題，其中每個單元格代表一個節點，節點間的移動成本交替變化。類似於在具有可變邊權重的加權圖上尋找最短路徑，此問題可有效地使用 Dijkstra 算法的變體來解決。

解法

我們基於優先隊列的遍歷方式，類似於 Dijkstra 算法，用於尋找橫跨網格的最短時間路徑。下列是涉及的步驟細分：

初始化：
- 我們維護一個 3D 的 visited 陣列，用於根據單元格座標和步驟奇偶性（即下一次移動需要1或2秒）來跟蹤狀態。
- 使用優先隊列（最小堆）存儲狀態，這些狀態為元組形式，包含負時間（以便彈出時優先考慮最小時間）、當前單元格座標（行，列）及步驟奇偶性（即下一次移動需要1或2秒）。
起始點：
- 我們從單元格 (0, 0) 開始搜索，以零時間和偶數奇偶性（下一步需要1秒）開始。
優先隊列處理：
- 主循環持續至優先隊列為空。
- 為每個從隊列中提取的狀態，檢查其是否已被訪問。如果是，則跳過以防止冗余計算。
- 如果達到目標單元格 (n-1, m-1)，返回目前的時間，因為它代表在考慮所有限制條件下最早可能訪問該單元格的時間。
探索相鄰單元格：
- 從當前單元格開始，嘗試移動到其四個相鄰的單元格（右、下、左、上）。
- 確保任何移動都在網格邊界內。
- 計算到新單元格的 arrival_time。它考慮到進入單元格所需的最大 moveTime 和當前時間加上所需移動時間（取決於奇偶性為1或2秒）。
- 然後將新狀態推入優先隊列以供進一步探索。
結束條件：
- 如果達到目標單元格 (n-1, m-1)，則立即返回計算出的最小時間。
- 如果優先隊列耗盡且未達到目標，這表示在任何有效路徑中該單元格均無法到達，然而此情況受到問題條件的約束。在這種情況下，返回 -1。

該算法通過優先考慮提供更早訪問任何單元格的路徑來高效地探索僅必需的路徑，並確保使用最小遍歷時間。交替的步驟時間通過交替奇偶性和調整遍歷成本進行管理。

程式碼

C++

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n = moveTime.size(); // 獲取行數
        int m = moveTime[0].size(); // 獲取列數

        // 3D向量用於記錄已訪問的狀態，具有奇偶性0和1
        vector<vector<vector<bool>>> visited(n, vector<vector<bool>>(m, vector<bool>(2, false)));

        // 方向向量用來在網格中移動：右，下，左，上
        int moves[] = {1, 0, -1, 0, 1};

        // 最小堆（優先佇列）存儲狀態，包含元組(負時間，行，列，奇偶性)
        priority_queue<tuple<int, int, int, int>> pq;
        pq.push({0, 0, 0, 0}); // 從(0,0)開始，時間為0，奇偶性為0

        while (!pq.empty()) {
            auto [neg_time, y, x, parity] = pq.top(); // 擷取當前狀態
            pq.pop();

            // 如果當前的格子及其奇偶性已被訪問，則跳過處理
            if (visited[y][x][parity]) continue;
            visited[y][x][parity] = true; // 標記當前狀態為已訪問

            // 如果達到目標格子（右下角），返回時間
            if (y == n - 1 && x == m - 1) return -neg_time;

            // 探索相鄰的格子
            for (int i = 0; i < 4; ++i) {
                int ny = y + moves[i]; // 新的行索引
                int nx = x + moves[i + 1]; // 新的列索引

                // 檢查新索引是否在邊界內
                if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;

                // 計算到新格子的到達時間
                int arrival_time = max(-neg_time, moveTime[ny][nx]) + (parity == 0 ? 1 : 2);

                // 將新狀態推入優先佇列
                pq.push({-arrival_time, ny, nx, 1 - parity});
            }
        }

        return -1; // 返回-1表示目標格子(n-1, m-1)不可達
    }
};

Python

class Solution:
    def minTimeToReach(self, moveTime):
        n = len(moveTime)  # 行數
        m = len(moveTime[0])  # 列數

        # 3D列表以追蹤已訪問的狀態，包含奇偶性0和1
        visited = [[[False, False] for _ in range(m)] for _ in range(n)]

        # 用於計算在網格中移動的方向：右、下、左、上
        moves = [1, 0, -1, 0, 1]

        # 最小堆（優先隊列）以元組形式儲存狀態：（負的時間，行，列，奇偶性）
        from heapq import heappush, heappop
        pq = []
        heappush(pq, (0, 0, 0, 0))  # 從(0,0)開始，時間為0且奇偶性為0

        while pq:
            neg_time, y, x, parity = heappop(pq)  # 提取當前狀態

            # 如果該單元格及其奇偶性已被訪問，則跳過處理
            if visited[y][x][parity]:
                continue
            visited[y][x][parity] = True  # 標記當前狀態為已訪問

            # 如果抵達目標單元格（右下角），返回時間
            if y == n - 1 and x == m - 1:
                return -neg_time

            # 探索相鄰的單元格
            for i in range(4):
                ny = y + moves[i]  # 新的行索引
                nx = x + moves[i + 1]  # 新的列索引

                # 檢查新索引是否在範圍內
                if ny < 0 or ny >= n or nx < 0 or nx >= m:
                    continue

                # 計算到達新單元格的時間
                arrival_time = max(-neg_time, moveTime[ny][nx]) + (1 if parity == 0 else 2)

                # 將新狀態壓入優先隊列
                heappush(pq, (-arrival_time, ny, nx, 1 - parity))

        return -1  # 如果目標單元格(n-1, m-1)不可達，返回-1

複雜度分析

時間複雜度: $O(n \times m \times \log(n \times m))$
該演算法利用優先佇列來探索網格，將其視為圖，每個節點（單元）最多有 4 個鄰居。考慮到有 $n \times m$ 個單元，每次在優先佇列（堆）上的推入或彈出操作需要 $O(\log(n \times m))$ 的時間。因此由於每條邊（移動）僅被處理一次，總體時間複雜度為 $O(n \times m \times \log(n \times m))$。
空間複雜度: $O(n \times m)$
空間複雜度主要由 visited 三維向量和優先佇列的存儲需求主導，維護每個網格單元的狀態資訊。儘管每個單元存儲了兩個奇偶狀態，但總體空間仍然是 $O(n \times m)$。優先佇列可能會容納 $O(n \times m)$ 個元素，但由於優先級順序，其大小通常較小。

CS Note
En

Leetcode 3342. Find Minimum Time to Reach Last Room II

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析