我最近在一次采访中被问到这个问题，我不知道如何实现它。我希望有人能给我指出解决这个问题的正确方向。
问题陈述：给定一个二维整数数组，找出可以容纳的总水量。数字表示地图中的海拔高度（即山的高度）。水从最高的山流向山谷（从最高到最低）。
例1：这是一个5 x 3矩阵。10是最高峰。您可以假设水向下流动，并在坐标(3, 1)处的瓷砖2开始收集。这块瓷砖能收集7单位的水。在以坐标(2, 0) or (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
在这种情况下，水可以按以下坐标收集：
（3，1）和（3，2）。所以总容量=>7+7=14
（1，4）（2，4）和（3，4）。这些坐标可以分别存储2、1、1。因为在水开始以坐标（1，5）从边缘溢出之前，它们能容纳的最大值是4。所以总容量=>2+1+1=4
总容量为14+4=18。
我试着用洪水来解决这个问题。通过找到从最高点到最低点的路径，并使用此路径来确定可以在最低高度存储的水。我不确定我是否走对了路。对如何解决这个问题有什么想法吗？
最佳答案
你在洪水泛滥的正确道路上。这里有一个解决问题的方法。
首先，将所有边缘瓷砖标记为完工。
然后创建内部平铺的排序列表，首先是最低的。
对列表中的每个平铺执行洪水填充
查找与最低平铺（山谷平铺）处于同一级别的所有平铺
查找最小的周围平铺（出口平铺）
确定是否已完成任何出口平铺
然后增加山谷瓷砖的级别以匹配出口瓷砖的级别。如果出口瓷砖已完成，则所有山谷瓷砖现在都已完成。否则，扩展山谷以包括出口瓷砖。
下面是算法如何处理问题的第二个例子。最初，边缘瓷砖是成品，而内部瓷砖不是。
假设右上角的2是第一个。出口瓷砖是3。所以把2增加到a 3，在总水量中加1。将3s增加到4，总水量增加3。四个已经完成了，所以山谷现在也结束了。
下一个是左下角的一个2。洪水漫灌会发现两个山谷瓦片，出口瓦片是9。所以我们可以加7到2块瓷砖，加14块水。其中一个出口完工了，所以山谷现在完工了。
在这一点上，每一个剩余的瓷砖相邻的出口瓷砖是相等或更低，也完成了。所以所有剩余的瓷砖都标记为完工。总水量为1+3+14=18。