二维数组中的总水容量，表示地形图
Total water capacity in a 2D array, which represents a topographical map
我最近在面试中被问到这个问题，但我不知道如何实现它。我希望有人能指出正确的方向来解决这个问题。
问题陈述：给定一个二维整数数组，找出可以容纳的水总量。这些数字代表地图中的海拔高度（即山的高度）。水从最高的山流向山谷（最高处到最低处）。
示例 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 增加到 3，总水量增加 1。然后3s可以增加到4，总水量加3。 4 完成了，所以那个山谷现在也完成了。
下一个是左下方的 2 之一。洪水填充会找到两个山谷瓦片，而出口瓦片是 9。所以我们可以将 7 加到两个瓦片上，使总水量增加 14。其中一个出口已经完工，所以那个山谷现在已经完工了。
在这一点上，每个剩余的瓷砖都与一个相等或更低的出口瓷砖相邻，并且也完成了。因此，所有剩余的图块都标记为已完成。而水的总和是1+3+14 = 18.
我最近在面试中被问到这个问题，但我不知道如何实现它。我希望有人能指出正确的方向来解决这个问题。
问题陈述：给定一个二维整数数组，找出可以容纳的水总量。这些数字代表地图中的海拔高度（即山的高度）。水从最高的山流向山谷（最高处到最低处）。
示例 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 增加到 3，总水量增加 1。然后3s可以增加到4，总水量加3。 4 完成了，所以那个山谷现在也完成了。
下一个是左下方的 2 之一。洪水填充会找到两个山谷瓦片，而出口瓦片是 9。所以我们可以将 7 加到两个瓦片上，使总水量增加 14。其中一个出口已经完工，所以那个山谷现在已经完工了。
在这一点上，每个剩余的瓷砖都与一个相等或更低的出口瓷砖相邻，并且也完成了。因此，所有剩余的图块都标记为已完成。而水的总和是1+3+14 = 18.