在网格中创建至少一条有效路径的最低成本

1368。在网格中创建至少一条有效路径的最低成本

难度：难

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

给定一个 m x n 网格。网格的每个单元格都有一个标志，指向您应该访问的下一个单元格（如果您当前位于该单元格中）。 grid[i][j] 的符号可以是：

• 1 表示转到右侧的单元格。 （即从 grid[i][j] 到 grid[i][j 1]）
• 2 表示转到左侧的单元格。 （即从 grid[i][j] 到 grid[i][j - 1]）
• 3 表示转到下面的单元格。 （即从 grid[i][j] 到 grid[i 1][j]）
• 4 表示转到上面的单元格。 （即从 grid[i][j] 到 grid[i - 1][j]）

请注意，网格单元格上可能有一些指向网格外部的标志。

您最初将从左上角的单元格 (0, 0) 开始。网格中的有效路径是沿着网格上的符号从左上角单元格 (0, 0) 开始，到右下角单元格 (m - 1, n - 1) 结束的路径。有效路径不一定是最短的。

您可以修改单元格上的符号，成本 = 1。您只能修改单元格上的符号一次。

返回使网格具有至少一条有效路径的最小成本.

示例1：

• 输入： grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2] ]
• 输出： 3
• 解释：您将从点 (0, 0) 开始。 到(3, 3)的路径如下。 (0, 0) --> (0, 1) --> (0, 2) --> (0, 3)
• 将箭头更改为向下，成本 = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0)
• 将箭头更改为向下，成本 = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3)
• 将箭头更改为向下，成本 = 1 --> (3, 3) 总成本 = 3.

示例2：

• 输入： grid = [[1,1,3],[3,2,2],[1,1,4]]
• 输出： 0
• 说明：您可以沿着从 (0, 0) 到 (2, 2) 的路径。

示例 3：

• 输入： grid = [[1,2],[4,3]]
• 输出： 1

约束：

• m == grid.length
• n == grid[i].length
• 1
• 1

提示：

1. 构建一个图，其中 grid[i][j] 通过加权边缘连接到所有四个侧相邻单元格。如果符号指向相邻单元格，则权重为 0，否则为 1。
2. 首先从 (0, 0) 访问所有权重 = 0 的边进行 BFS。答案是到 (m -1, n - 1) 的距离。

解决方案：

我们可以使用0-1 BFS方法。这个想法是使用双端队列（双端队列）遍历网格，其中修改方向的成本决定将单元格添加到双端队列的前面还是后面。网格被视为一个图表，其中每个单元格根据其当前方向是否与其邻居的移动相匹配而具有加权边缘。

让我们用 PHP 实现这个解决方案：1368。在网格中创建至少一条有效路径的最低成本

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

// Example Test Cases
$在网格中创建至少一条有效路径的最低成本 = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]];
echo minCost($在网格中创建至少一条有效路径的最低成本) . "\n"; // Output: 3

$在网格中创建至少一条有效路径的最低成本 = [[1,1,3],[3,2,2],[1,1,4]];
echo minCost($在网格中创建至少一条有效路径的最低成本) . "\n"; // Output: 0

$在网格中创建至少一条有效路径的最低成本 = [[1,2],[4,3]];
echo minCost($在网格中创建至少一条有效路径的最低成本) . "\n"; // Output: 1
?>

解释：

1. 方向映射： 每个方向（1 向右、2 向左、3 向下、4 向上）都映射到运动增量数组 [dx, dy]。

2. 0-1 BFS：

   • 双端队列用于对成本较低的单元进行优先级排序。不需要修改方向的单元格添加到前面（unshift），而需要修改方向的单元格添加到后面（入队）。
   • 这确保了单元按照成本递增的顺序进行处理。

3. 距离数组： 二维数组 $dist 跟踪到达每个单元格的最小成本。除起始单元格 (0, 0) 之外的所有单元格均使用 PHP_INT_MAX 进行初始化。

4. 边权重：

   • 如果当前单元格的符号与预期方向匹配，则成本保持不变。
   • 否则修改方向的成本为1。

5. 终止： 一旦处理完所有单元格，循环就会终止。结果是$dist[$m - 1][$n - 1]中的值，代表到达右下角的最小成本。

复杂：

• 时间复杂度： O(m × n)，因为每个单元格都被处理一次。
• 空间复杂度： O(m × n)，对于距离数组和双端队列。

联系链接

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

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

• 领英
• GitHub

以上是在网格中创建至少一条有效路径的最低成本的详细内容。更多信息请关注PHP中文网其他相关文章！