最高峰地圖

1765。最高峰地圖

難度：中

主題：陣列、廣度優先搜尋、矩陣

給定一個大小為 m x n 的整數矩陣 isWater，它表示 land 和 water 單元格的地圖。

• 如果 isWater[i][j] == 0，則單元格 (i, j) 是陸地單元格。
• 如果 isWater[i][j] == 1，則單元格 (i, j) 是水單元格。

您必須依照下列規則為每個儲存格指派高度：

• 每個單元格的高度必須為非負數。
• 如果單元格是水單元格，則其高度必須為 0。
• 任何兩個相鄰單元格的絕對高度差必須最多 1。如果一個單元格位於另一個單元格的正北、東、南或西方向，則該單元格與另一個單元格相鄰（即，他們的側面接觸）。

找出一個高度分配，使得矩陣中的最大高度為最大化.

傳回大小為 m x n 的整數矩陣高度，其中 height[i][j] 是單元格 (i, j) 的高度。如果有多個解決方案，則傳回其中任何。

範例1：

• 輸入： isWater = [[0,1],[0,0]]
• 輸出： [[1,0],[2,1]]
• 說明： 影像顯示了每個單元格的指定高度。
  • 藍色單元格是水單元格，綠色單元格是陸地單元格。

範例2：

• 輸入： isWater = [[0,0,1],[1,0,0],[0,0,0]]
• 輸出： [[1,1,0],[0,1,1],[1,2,2]]
• 解釋： 高度 2 是任何分配的最大可能高度。
  • 任何最大高度為 2 且仍符合規則的高度分配也將被接受。

範例 3：

• 輸入： isWater = [[1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0, 0,0,1,1,0, 0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0 ,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0 ,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0, 0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1, 0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0 ,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0 ,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0, 0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0 ,0,1,0,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,1,0,0,0,1 ,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0, 0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1, 0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1 ,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0 ,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1, 1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0, 0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,1 ,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0, 1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0] ,[0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1 ,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0 ,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0, 0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0, 0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1 ,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0 ,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0, 1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1, 0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1 ,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1 ,0,1,1,0,0,0,0,1,0,1,0,0],...]
• 輸出： [[0,1,2,2,2,1,0,1,1,0,1,1,0,1,2,1,1,2,2,1, 1,0,0,1, 2,1,1,2,2,1,0 ,1,1,0,1,0,0,1,1,0,1,0,1,2,2,1,1,1,0,1,1,1,0,0,1,1 ,1,2,1,0,1,2, 3,2,1,1,0,1,1,0,1,2,2,1,2,2,1,0,1,1,0 ,1,2,1,0,0,1, 2,1,0,1,1,0,1 ,0,0,1,2,1,0,1,0,0,0,1,1,0,1,1,1,0,0, 1,0,1,1,1,0,1 ,1,0,1,1,2,1, 0,1,0,1,0,0,1,2,1,2,3,3,2,2,1,0,0,0,1,1,1,0,1,1,0, 1,1,0,1,0,1,0 ,1,0,0,1,2,1,1,2,2,1,0,0,0,1,0,1,1,2, 3,2,2,2,2,2,2 ,3,2,3,3,2,1, 0,1,2,1,1,2,1,0,1,0,0,0,1,1,0,1,2,3,2 ,1,0,1,2,1,1, 0,1,1,0,1,2], [0,0,1,1,2,2,1,0,1,1,1,0,1,2,1,0,0,1,1,0,1,1,0,0,1 ,0,0,1,1,0,0, 1,1,1,0,1,1,1,1,0,1,1,2,2,1,0,0,1,1,1 ,0,1,0,1,1,0, 0,1,2,1,0,1,2 ,1,0,0,1,0,1,0,1,2,1,0,1,1,0,0,0,0,1, 2,3,2,1,1,0,1 ,1,1,1,0,1,0, 1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,0,0, 1,1,1,0,1,0,1 ,2,1,1,0,0,0,1,0,1,2,2,1,1,0,1,0,1,1, 0,1,1,1,1,0,1 ,0,0,1,1,1,0, 0,0,1,2,1,0,0,1,1,0,1,0,1,2,1,1,0,1,2 ,1,1,1,1,1,1, 2,1,2,3,3,2,1 ,0,1,0,0,1,0,1,0,0,1,0,1,2,1,2,3,2,1,1,0,1,1,0,1,0 ,1,2,1,2,3],[ 1,1,0,0,1,1,0,1,1,2,1,0,1,1,1,0,1,0,1 ,0,1,1,0,1,2, 1,1,0,1,1,1,1 ,0,1,1,2,1,0,1,1,2,1,2,2,1,1,0,1,0,1, 0,1,1,2,1,0,1 ,2,1,...]]

約束：

• m == isWater.length
• n == isWater[i].length
• 1
• isWater[i][j] 是 0 或 1。
• 至少有一個個水細胞。

提示：

1. 將每個水單元設定為 0。每個單元的高度受其最近的水單元的限制。
2. 以所有水細胞為源執行多源 BFS。

註：本題與542.01矩陣相同

解：

我們可以使用廣度優先搜尋（BFS）方法。以下是我們如何逐步實現它：

問題分解：

1. 水細胞：帶有1的細胞代表水細胞，其高度始終為0。
2. 陸地單元：帶有 0 的單元代表陸地單元，其高度應指定為使得相鄰陸地單元的高度差最多為 1。

方法：

1. BFS 初始化:

   • 我們首先將所有水單元格（值為 1 的單元格）標記為 BFS 中的起點，並將它們的高度指定為 0。
   • 然後我們處理鄰近的陸地單元（值為 0 的單元）以分配高度。

2. BFS 遍歷:

   • 從每個水單元開始，我們向外擴展，將每個相鄰的陸地單元的高度增加 1，確保相鄰單元之間的高度差永遠不會超過 1。
   • 我們繼續這個過程，直到訪問完所有單元格。

3. 結果：結果將是遵循給定規則的高度矩陣，其中高度值最大化。

讓我們用 PHP 實作這個解：1765。最高峰地圖

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

// Example usage:
$$isWater1 = [[0,1],[0,0]];
$$isWater2 = [[0,0,1],[1,0,0],[0,0,0]];
$$isWater3 = [[1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0],[0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0],...];

echo highestPeak($$isWater1) . "\n"; // Output: [[1,0],[2,1]]
echo highestPeak($$isWater2) . "\n"; // Output: [[1,1,0],[0,1,1],[1,2,2]]
echo highestPeak($$isWater3) . "\n"; // Output: [[0,1,2,2,2,1,0,1,1,0,1,1,0,1,2,1,1,2,2,1,1,0,0,1,2,1,1,2,2,1,0,1,1,0,1,0,0,1,1,0,1,0,1,2,2,1,1,1,0,1,1,1,0,0,1,1,1,2,1,0,1,2,3,2,1,1,0,1,1,0,1,2,2,1,2,2,1,0,1,1,0,1,2,1,0,0,1,2,1,0,1,1,0,1,0,0,1,2,1,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,1,1,1,0,1,1,0,1,1,2,1,0,1,0,1,0,0,1,2,1,2,3,3,2,2,1,0,0,0,1,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,0,1,2,1,1,2,2,1,0,0,0,1,0,1,1,2,3,2,2,2,2,2,2,3,2,3,3,2,1,0,1,2,1,1,2,1,0,1,0,0,0,1,1,0,1,2,3,2,1,0,1,2,1,1,0,1,1,0,1,2],[0,0,1,1,2,2,1,0,1,1,1,0,1,2,1,0,0,1,1,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,0,1,1,1,1,0,1,1,2,2,1,0,0,1,1,1,0,1,0,1,1,0,0,1,2,1,0,1,2,1,0,0,1,0,1,0,1,2,1,0,1,1,0,0,0,0,1,2,3,2,1,1,0,1,1,1,1,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,0,1,1,1,0,1,0,1,2,1,1,0,0,0,1,0,1,2,2,1,1,0,1,0,1,1,0,1,1,1,1,0,1,0,0,1,1,1,0,0,0,1,2,1,0,0,1,1,0,1,0,1,2,1,1,0,1,2,1,1,1,1,1,1,2,1,2,3,3,2,1,0,1,0,0,1,0,1,0,0,1,0,1,2,1,2,3,2,1,1,0,1,1,0,1,0,1,2,1,2,3],[1,1,0,0,1,1,0,1,1,2,1,0,1,1,1,0,1,0,1,0,1,1,0,1,2,1,1,0,1,1,1,1,0,1,1,2,1,0,1,1,2,1,2,2,1,1,0,1,0,1,0,1,1,2,1,0,1,2,1,...]]
?>

解釋：

1. 初始化:

   • 我們將所有單元格的高度矩陣初始化為 -1。水細胞立即設定為 0。
   • 水細胞被排入 BFS 隊列。

2. BFS:

   • 我們透過使每個單元出列來處理隊列，並且對於其每個相鄰單元，我們檢查它是否在邊界內並且未被訪問。
   • 如果它是有效的陸地單元（未訪問過），我們會為其分配比當前單元高度大一的高度，並將其排隊以進行進一步處理。

3. 結果：

   • BFS 完成後，高度矩陣將包含每個單元格的最高可能高度，尊重給定的限制。

時間複雜度：

• O(m * n) 其中 m 是行數，n 是列數。這是因為在 BFS 遍歷過程中每個單元最多被處理一次。

此解決方案確保矩陣填滿正確的高度，並且 BFS 保證每個單元格的最大高度，同時保持相鄰單元格之間的高度差約束。

聯絡連結

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

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

• 領英
• GitHub

以上是最高峰地圖的詳細內容。更多資訊請關注PHP中文網其他相關文章！