最高峰地图

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,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],...]
• 输出： [[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,...]]

约束：

• 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中文网其他相关文章！