2D阵列中的总水容量,表示地形图
yes*_*esh 6 algorithm flood-fill
我最近在一次采访中被问到了这个问题,我无法弄清楚如何实现它.我希望有人能指出我如何处理这个问题的正确方向.
问题陈述:给定2D整数数组,找到可以容纳的总水量.数字代表地图中的高程(即山峰的高度).水从最高的山流到山谷(最高的高度到最低的高度).
例1:这是一个5 x 3矩阵.10是最高峰.你可以假设水流下来并开始收集在坐标2的瓷砖上(3, 1).这块瓷砖将收集7个单位的水.在以坐标溢出到高度为9的相邻瓷砖(2, 0) or (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
在这种情况下,水可以在以下坐标中收集:
- (3,1)和(3,2).所以总容量=> 7 + 7 = 14
- (1,4)(2,4)和(3,4).这些坐标可以分别存储2,1,1.因为在水开始从坐标边缘溢出之前它们可以保持的最大值为4(1,5).所以总容量=> 2 + 1 + 1 = 4
超过所有容量是14 + 4 = 18.
我尝试使用洪水填充来解决这个问题.通过找到从最高峰到最低的路径,并使用此路径确定可以存储在最低高度的水.我不确定我是否走在正确的道路上.有关如何解决这个问题的任何想法？
您走在正确的道路上，洪水已被填满。这是解决该问题的一种方法。
首先，将所有边缘瓷砖标记为已完成。
然后创建内部图块的排序列表，最低的在前。
对于列表中的每个图块执行洪水填充
- 查找与最低瓷砖（山谷瓷砖）处于同一水平的所有瓷砖
- 找到最小的周围瓦片（出口瓦片）
- 确定是否有任何出口瓷砖已经完成
然后增加山谷瓷砖的水平以匹配出口瓷砖的水平。如果出口瓷砖完成，那么所有山谷瓷砖现在都完成了。否则，扩大山谷以包括出口瓷砖。
以下是该算法如何处理问题的第二个示例。最初，边缘瓷砖已完成，而内部瓷砖尚未完成。
假设右上角的2是第一个。出口瓷砖是 3。因此，将 2 增加到 3，将 1 添加到总水量中。然后可以将 3s 增加到 4，将 3 加入到总水量中。4 已经完成，所以那个山谷现在已经完成了。
接下来是左下角的 2 之一。洪水填充会找到两个山谷瓷砖，出水口瓷砖是 9。因此我们可以将 7 添加到两个瓷砖，将 14 添加到总水量中。其中一个出口已经完工，因此山谷现已完工。
此时，每个剩余的瓷砖都与相同或更低的出口瓷砖相邻，并且也已完成。因此，所有剩余的图块都标记为已完成。总水量为 1+3+14 = 18。