到达拐角所需清除的障碍物最少

2290。最少清除障碍物才能到达拐角

难度：难

主题：数组、广度优先搜索、图、堆（优先级队列）、矩阵、最短路径

给你一个 0 索引 大小为 m x n 的 2D 整数数组网格。每个单元格都有两个值之一：

• 0 代表空单元格，
• 1 代表可以移除的障碍物。

您可以在空单元格之间向上、向下、向左或向右移动。

将最小个障碍物返回到移除，这样你就可以从左上角(0, 0)移动到右下角角 (m - 1, n - 1).

示例1：

• 输入： grid = [[0,1,1],[1,1,0],[1,1,0]]
• 输出： 2
• 解释：我们可以移除 (0, 1) 和 (0, 2) 处的障碍物，创建一条从 (0, 0) 到 (2, 2) 的路径。
  • 可以证明我们需要移除至少 2 个障碍物，因此我们返回 2。
  • 请注意，可能还有其他方法可以移除 2 个障碍物来创建一条路径。

示例2：

• 输入： grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
• 输出： 0
• 解释：我们可以在不移除任何障碍的情况下从 (0, 0) 移动到 (2, 4)，因此我们返回 0。

约束：

• m == grid.length
• n == grid[i].length
• 1 5
• 2 5
• grid[i][j] 为 0 或 1。
• 网格[0][0] == 网格[m - 1][n - 1] == 0

提示：

1. 将网格建模为图形，其中单元格是节点，边是相邻单元格之间的。有障碍物的单元格的边缘的成本为 1，所有其他边缘的成本为 0。
2. 你能使用0-1广度优先搜索或Dijkstra算法吗？

解决方案：

我们需要使用图表来模拟这个问题，其中网格中的每个单元格都是一个节点。目标是从左上角 (0, 0) 导航到右下角 (m-1, n-1)，同时最大限度地减少我们需要移除的障碍物 (1s) 的数量。

方法：

1. 图形表示：

   • 网格中的每个单元格都是一个节点。
   • 相邻单元格之间的移动（上、下、左、右）被视为边缘。
   • 如果一条边穿过带有 1（障碍物）的单元格，则成本为 1（移除障碍物），如果它穿过 0（空单元格），则成本为 0。

2. 算法选择：

   • 由于我们需要最小化移除的障碍物数量，因此我们可以使用 0-1 BFS（使用双端队列的广度优先搜索）或 Dijkstra 算法 以及优先级队列。
   • 0-1 BFS 适合这里，因为每条边的成本为 0 或 1。

3. 0-1 BFS：

   • 我们使用deque（双端队列）来处理不同成本的节点：
     • 将成本为 0 的单元推到双端队列的前面。
     • 将成本为 1 的单元推到双端队列的后面。
   • 这个想法是探索网格并始终先扩展不需要移除障碍物的路径，并且仅在必要时移除障碍物。

让我们用 PHP 实现这个解决方案：2290。到达拐角所需清除的最小障碍物

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

// Test Case 1
$grid1 = [
    [0, 1, 1],
    [1, 1, 0],
    [1, 1, 0]
];
echo minimumObstacles($grid1) . PHP_EOL; // Output: 2

// Test Case 2
$grid2 = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0]
];
echo minimumObstacles($grid2) . PHP_EOL; // Output: 0
?>

解释：

1. 输入解析：

   • 网格被视为二维数组。
   • 计算行和列以进行边界检查。

2. 双端队列实现：

   • SplDoublyLinkedList用于模拟双端队列。支持在前面（unshift）或后面（push）添加元素。

3. 已访问数组：

   • 跟踪已访问过的单元格以避免冗余处理。

4. 0-1 BFS 逻辑：

   • 从 (0, 0) 开始，成本为 0。
   • 对于每个相邻单元格：
     • 如果为空（grid[nx][ny] == 0），则以相同的成本将其添加到双端队列的前面。
     • 如果它是一个障碍物 (grid[nx][ny] == 1)，则将其添加到双端队列的后面，并增加成本。

5. 返回结果：

   • 到达右下角时，返回费用。
   • 如果不存在有效路径（尽管问题保证有一个），则返回 -1。

复杂：

• 时间复杂度： O(m x n)，其中 m 是行数，n 是列数。每个单元格都会被处理一次。
• 空间复杂度： O(m x n)，对于访问的数组和双端队列。

此实现在给定的限制内有效地工作。

联系链接

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

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

• 领英
• GitHub

以上是到达拐角所需清除的障碍物最少的详细内容。更多信息请关注PHP中文网其他相关文章！