访问网格中的单元的最短时间

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。访问网格中的单元格的最短时间

<?php /**
 * @param Integer[][] $grid
 * @return Integer
 */
function minimumTime($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$grid1 = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid1) . PHP_EOL; // Output: 7

// Example 2
$grid2 = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid2) . PHP_EOL; // Output: -1
?>

解释：

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).

---

运行示例

输入：

<?php /**
 * @param Integer[][] $grid
 * @return Integer
 */
function minimumTime($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$grid1 = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid1) . PHP_EOL; // Output: 7

// Example 2
$grid2 = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid2) . PHP_EOL; // Output: -1
?>

输入：

$grid = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid); // Output: 7

这个解决方案非常高效，并且在限制范围内运行良好。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是访问网格中的单元的最短时间的详细内容。更多信息请关注PHP中文网其他相关文章！