algorithm - 二维数组中的总水容量，表示地形图

Question

我最近在一次采访中被问到这个问题，但我不知道如何实现它。我希望有人能指出正确的方向来解决这个问题。

问题陈述:给定一个二维整数数组，找出可以容纳的水总量。这些数字代表 map 中的海拔高度(即山的高度)。水从最高的山流向山谷(最高处到最低处)。

示例 1:这是一个 5 x 3 矩阵。 10是最高峰。您可以假设水向下流动并开始在坐标为 (3, 1) 的图 block 2 处收集。这 block 瓷砖将收集 7 单位的水。在溢出到坐标 (2, 0) 或 (3, 0) 处高度为 9 的相邻图 block 并流入海洋之前(假设边缘被海洋包围)。因此，为这张 map 收集的总水量为 7。

9  9  9
9 10  9
9  9  9
9  2  10
10 10 10

示例 2:

    9   9  9  9  9 9
    9  10  9  8  2 4
    9   9  9 10  3 5
    9   2  2 10  3 5
   10 10  10 10  9 9

在这种情况下，水可以聚集在以下坐标中:

1. (3, 1) & (3, 2)。所以总容量 => 7 + 7 = 14
2. (1, 4) (2, 4) & (3, 4)。这些坐标可以分别存储2、1、1。因为在水开始从坐标 (1, 5) 处的边缘溢出之前，它们可以容纳的最大值是 4。所以总容量 => 2 + 1 + 1 = 4

总容量是 14 + 4 = 18。

我尝试使用洪水填充来解决这个问题。通过找到一条从最高峰到最低点的路径，并使用这条路径来确定可以在最低高度存储的水。我不确定我是否走在正确的道路上。关于如何解决这个问题有什么想法吗？

Answer 1

使用洪水填充，您走在正确的道路上。这是解决该问题的一种方法。

首先，将所有边缘瓷砖标记为已完成。

然后创建一个内部图 block 的排序列表，从小到大。

对于列表中的每个图 block 执行洪水填充

1. 找到与最低瓦片(山谷瓦片)处于同一级别的所有瓦片
2. 找到最小的周围瓦片(导出瓦片)
3. 确定是否有任何导出瓷砖已经完成

然后增加山谷瓷砖的水平以匹配导出瓷砖的水平。如果导出瓦片已完成，那么所有山谷瓦片现在都已完成。否则，扩大山谷以包括导出瓷砖。

---

下面是该算法如何处理问题中的第二个示例。最初，边缘瓷砖已完成，内部瓷砖尚未完成。

假设右上角的2是第一个。导出瓷砖是 3。因此将 2 增加到 3，总水量增加 1。然后3s可以增加到4，总水量加3。 4 结束了，所以那个山谷现在结束了。

下一个是左下方的 2 之一。洪水填充会找到两个山谷瓦片，而导出瓦片是 9。所以我们可以将 7 加到两个瓦片上，使总水量增加 14。其中一个导出已经完工，所以那个山谷现在已经完工了。

在这一点上，每个剩余的瓦片都与一个相等或更低的导出瓦片相邻，并且也已完成。因此，所有剩余的图 block 都标记为已完成。总水量为1+3+14 = 18。