在網格中建立至少一條有效路徑的最低成本

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中文網其他相關文章！