一个用于表示地形图的二维数组中的总水容量

Question

最近在面试中被问到这个问题，但我不知道如何实现。希望有人能指点我如何解决这个问题。

问题陈述：给定一个二维整数数组，找出其中可以容纳的总水量。数组中的数字代表地图上的高程（即山的高度）。水从最高峰流到山谷（从最高处到最低处的高度）。

示例 1：这是一个 5 x 3 的矩阵。10 是最高峰。你可以假设水向下流并开始在坐标为 (3, 1) 的格子处聚集。此格将收集7个单位的水。在溢出到高度为9的相邻格子 (2, 0) 或 (3, 0) 并流入海洋之前。所以这张地图收集到的总水量是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。因为它们最多能容纳4个单位的水，然后水就会从坐标(1, 5)的边缘溢出。因此总容量 => 2 + 1 + 1 = 4

总容量为14 + 4 = 18。

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

- yesh

---

这里有一个类似的一维问题：https://stackoverflow.com/questions/43398839/add-water-between-in-a-bar-chart/43403883 - m69 ''snarky and unwelcoming''

Answer 1

你使用泛洪填充算法是正确的。以下是解决问题的一种方法。

首先，将所有边缘瓦片标记为已完成。

然后创建一个按顺序排列的内部瓦片列表，最低的在前面。

对于列表中的每个瓦片，执行以下操作：

1. 找到与最低瓦片（山谷瓦片）相同级别的所有瓦片。 2. 找到周围最小的瓦片（出口瓦片）。 3. 确定任何出口瓦片是否已经完成。

然后将山谷瓦片的水平增加到与出口瓦片的水平相匹配。如果出口瓦片已经完成，则所有山谷瓦片现在都已完成。否则，扩展山谷以包括出口瓦片。

---

以下是算法如何处理问题中的第二个示例。最初，边缘瓦片已完成，内部瓦片未完成。

假设右上角的数字2是第一个，出口瓷砖是3。所以将2增加到3，总水量增加1。然后将3增加到4，总水量增加3。而4已经完成，所以那个山谷现在已经完成了。

下一个需要处理的是左下角的两个2中的一个。泛洪填充将找到两个低谷瓦片，出口瓦片为9。因此，我们可以将7添加到两个瓦片中，总共增加14个单位的水。其中一个出口已完成，所以该低谷现在已经完成。

此时，每个剩余的瓷砖都与高度相等或更低的插座砖相邻，并且已经完成。因此，所有剩余的瓷砖都被标记为已完成。总水量为1 + 3 + 14 = 18。

- user3386109