二维阵列中的总水量，表示地形图

Question

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

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

示例1：这是一个5 x 3的矩阵。10是最高峰。您可以假设水向下流动，并开始在坐标处的瓷砖2处收集。这块瓷砖将收集7单位的水。在坐标（2，0）或（3，0）处溢出至高度为9的相邻瓷砖并流入大海之前（假设边缘被大海包围）。所以这张地图收集的总水量是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）

总容量为14 4=18。

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

Answer 1

你在洪水泛滥的正确道路上。这里有一种解决问题的方法。

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

然后创建内部平铺的排序列表，首先是最下面的平铺。

对列表中的每个磁贴执行整体填充，以

1. 查找与最低平铺（山谷平铺）处于同一级别的所有平铺

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

下面是算法如何与问题中的第二个示例一起工作。最初，边缘图块完成，而内部图块没有完成。

假设右上角的2是第一个。出口瓷砖为3。因此，将2增加到3，将1添加到总水量中。然后3s可以增加到4，总水量增加3。4号完成了，所以山谷现在完成了。

接下来是左下角的2之一。洪水填充会找到两个山谷瓦片，出口瓦片是9。所以我们可以在两个瓦片上添加7，在总水量上添加14。其中一个出口完成了，所以山谷现在完成了。

在这一点上，每个剩余的瓷砖都与同等或更低的出口瓷砖相邻，并且也已完成。因此，所有剩余的瓷砖都标记为完工。总水量为1 3 14=18。