存取網格中的單元的最短時間

2577。存取網格中的單元格的最短時間

難度：難

主題：陣列、廣度優先搜尋、圖、堆疊（優先權佇列）、矩陣、最短路徑

給定一個m x n 矩陣網格，由非負 整數組成，其中grid[row][col] 表示能夠存取單元格所需的最短 時間（行、 col)，表示只有存取儲存格(row, col)的時間大於等於grid[row][col]，才能存取該儲存格。

您在第0 秒站在矩陣的^左上角 單元格中，並且您必須移動到四個中任何 相鄰單元格方向：上、下、左、右。你的每一個動作都需要 1 秒。

傳回存取矩陣右下儲存格所需的最短時間。如果無法存取右下角的儲存格，則傳回 -1.

範例1：

• 輸入： grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
• 輸出： 7
• 說明：我們可以採取的路徑之一如下：
  • 在 t = 0 時，我們位於單元 (0,0) 上。
  • 在 t = 1 時，我們移動到單元格 (0,1)。這是可能的，因為 grid[0][1]
  • 在 t = 2 時，我們移動到單元格 (1,1)。這是可能的，因為 grid[1][1]
  • 在 t = 3 時，我們移動到單元格 (1,2)。這是可能的，因為 grid[1][2]
  • 在 t = 4 時，我們移動到單元格 (1,1)。這是可能的，因為 grid[1][1]
  • 在 t = 5 時，我們移動到單元格 (1,2)。這是可能的，因為 grid[1][2]
  • 在 t = 6 時，我們移動到單元格 (1,3)。這是可能的，因為 grid[1][3]
  • 在 t = 7 時，我們移動到單元格 (2,3)。這是可能的，因為 grid[2][3]
  • 最終時間是7。可以證明這是可能的最短時間。

範例2：

• 輸入： grid = [[0,2,4],[3,2,1],[1,0,4]]
• 輸出： -1
• 解釋：沒有從左上角到右下角單元格的路徑。

約束：

• m == grid.length
• n == grid[i].length
• 2
• 4 sup>5
• 0 sup>5
• 格[0][0] == 0

提示：

1. 嘗試使用某種演算法來找出圖表上的最短路徑。
2. 考慮這樣的情況：您必須在矩陣的兩個單元之間來回移動才能解鎖其他一些單元。

解：

我們可以使用優先權佇列應用Dijkstra演算法的修改版本。這個問題本質上要求我們找到從左上角單元格存取右下角單元格所需的最短時間，其中每次移動都有基於網格中的值的時間限制。

方法：

1. 圖形表示：將網格中的每個單元格視為一個節點。邊緣是您可以移動到的相鄰單元格（上、下、左、右）。

2. 優先權佇列（最小堆）：使用優先權佇列始終以最少的時間探索單元。這確保我們按照最早到達細胞的順序處理細胞。

3. 修改後的 BFS：對於每個單元格，我們將檢查是否可以移動到其相鄰單元格並更新我們可以訪問它們的時間。如果某個儲存格在比目前時間晚的時間被訪問，我們將使用新時間將其新增回佇列中。

4. 提前退出：一旦到達右下角的儲存格，我們就可以返回時間。如果我們耗盡隊列但未到達，則傳回 -1。

讓我們用 PHP 實作這個解決方案：2577。存取網格中的單元格的最短時間

解釋：

1. 優先隊列:
   
   SplPriorityQueue 用於確保首先處理時間最短的單元。優先權儲存為 -time，因為 PHP 的 SplPriorityQueue 預設是最大堆。

2. 遍歷:
   
   從左上角的單元格(0, 0) 開始，演算法處理所有可到達的單元格，考慮每個單元格可以被存取的最早時間(max(0, grid[newRow][newCol] - (time 1) ))。

3. 存取的儲存格:
   
   訪問過的數組會追蹤已經處理過的單元格，以避免冗餘計算和無限循環。

4. 邊界和有效性檢查:
   
   此演算法確保我們保持在網格範圍內並僅處理有效的鄰居。

5. 時間計算:
   
   每次移動需要一秒鐘，如果單元格需要等待（即 grid[newRow][newCol] > 時間 1），演算法會等待，直到所需的時間。

6. 邊緣案例：
   
   如果佇列已耗盡且未到達右下儲存格，則函數傳回 -1。

---

複雜性分析

1. 時間複雜度:

   • 每個單元最多加入優先權佇列一次：O(m x n x log(m x n))，其中m和n 是網格尺寸。

2. 空間複雜度:

   • 優先權佇列與存取陣列的空間為O(m x n).

---

運行範例

輸入：

輸入：

這個解決方案非常高效，並且在限制範圍內運作良好。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是存取網格中的單元的最短時間的詳細內容。更多資訊請關注PHP中文網其他相關文章！