java - 二维数组的水容量

Question

我必须在我的大学做一些运动，但我已经困了一段时间了。练习是关于计算二维数组的水容量，用户必须输入二维数组的宽度(w)和高度(h)，然后是数组的所有元素，代表该位置的高度.非常简单的例子:

10 10 10
10 2 10
10 10 10

然后输出将为 8，因为这是适合其中的最大水量。另一个例子是:

 6 4
 1 5 1 5 4 3
 5 1 5 1 2 4
 1 5 1 4 1 5
 3 1 3 6 4 1

输出将为 14。

另外需要注意的是:数组的宽度和高度不能大于1000，元素的高度不能大于10^5。

现在我基本上有了解决方案，但是对于更大的输入来说它不够快。我所做的如下:我将高度添加到 TreeSet，然后每次我轮询最后一个(最高)然后我遍历数组(不看边缘)并使用 DFS 并检查每个位置是否水可以留在里面。如果水没有超出阵列，则计算水下的位置，如果超出阵列，则再次轮询并执行相同操作。

我还尝试通过垂直和水平方向查看阵列中的峰值。对于上面的例子，你得到这个:

0 5 0 5 4 0
5 0 5 0 0 4
0 5 0 4 0 5
3 1 3 6 4 0

我用这个做的是给峰一个颜色，比如说(黑色)，然后对于所有的白色再次用 DFS 取最小峰值，然后取最小值来计算水容量。但这不起作用，因为例如:

7 7 7 7 7
7 4 4 4 7
7 2 3 1 7
7 4 4 4 7
7 7 7 7 7

现在3是一个高峰，但是到处都是7水位。所以这行不通。

但是因为我的解决方案不够快，所以我正在寻找更高效的解决方案。这是神奇发生的代码部分:

    while (p.size() != 0 || numberOfNodesVisited!= (w-2)*(h-2)) {
        max = p.pollLast();
        for (int i=1; i < h-1; i++) {
            for (int j=1; j < w-1; j++) {
                if (color[i][j] == 0) {
                    DFSVisit(profile, i, j);
                    if (!waterIsOut) {
                        sum+= solveSubProblem(heights, max);
                        numberOfNodesVisited += heights.size();
                        for(int x = 0; x < color.length; x++) {
                            color2[x] = color[x].clone();
                        }
                    } else {
                        for(int x = 0; x < color2.length; x++) {
                            color[x] = color2[x].clone();
                        }
                        waterIsOut = false;
                    }
                    heights.clear();
                }
            }
        }
   }

请注意，我每次都会重新设置路径和颜色，我认为这是必须改进的部分。

我的 DFS:我有三种颜色 2(黑色)它被访问，1(灰色)如果它是边缘，0(白色)如果没有被访问并且不是边缘。

 public void DFSVisit(int[][] profile, int i, int j) {
    color[i][j] = 2; // black
    heights.add(profile[i][j]);
    if (!waterIsOut && heights.size() < 500) { 
        if (color[i+1][j] == 0 && max > profile[i+1][j]) { // up
            DFSVisit(profile, i+1, j);
        } else if (color[i+1][j] == 1 && max > profile[i+1][j]) {
            waterIsOut = true;
        }
        if (color[i-1][j] == 0 && max > profile[i-1][j]) { // down
            DFSVisit(profile, i-1, j);
        } else if (color[i-1][j] == 1 && max > profile[i-1][j]) {
            waterIsOut = true;
        }
        if (color[i][j+1] == 0 && max > profile[i][j+1]) { // right
            DFSVisit(profile, i, j+1);
        } else if (color[i][j+1] == 1  && max > profile[i][j+1]) {
            waterIsOut = true;
        }
        if (color[i][j-1] == 0  && max > profile[i][j-1]) { //left
            DFSVisit(profile, i, j-1);
        } else if (color[i][j-1] == 1  && max > profile[i][j-1]) {
            waterIsOut = true;
        }
    }
}

更新 @dufresnb 提到了 talentbuddy.co，在 https://www.talentbuddy.co/challenge/526efd7f4af0110af3836603 给出了同样的练习。 .然而，我测试了很多解决方案，其中一些实际上通过了我的前四个测试用例，但是大多数已经在简单的测试上失败了。人才伙伴在制作测试用例方面做得很糟糕:实际上他们只有两个。如果你想看他们刚刚注册并输入这段代码(C语言)的解决方案:通过他们的测试用例就足够了

#include <stdio.h>

void rain(int m, int *heights, int heights_length) {
    //What tests do we have here?
    if (m==6)
        printf("5");
    else if (m==3)
        printf("4");
    //Looks like we need some more tests.
}

更新 @tobias_k 解决方案是一个可行的解决方案，但是就像我的解决方案一样，它的效率不足以通过更大的输入测试用例，有没有人有更有效的实现的想法？

任何想法和帮助将不胜感激。

Answer 1

这是我对这个问题的看法。思路如下:你反复flood-fill该阵列使用增加的“海平面”。一个节点第一次被淹没的水位与“洪水”退去时该节点上方积水的水位相同。

• 对于从最低到最高级别的每个高度:
  • 将外部节点放入一个集合中，称为边缘
  • 当边缘集中有更多节点时，从集合中弹出一个节点
    • 如果在本次迭代中首先到达该节点并且其高度小于或等于当前洪水高度，则记住该节点的当前洪水高度
    • 将所有尚未被淹没且高度小于或等于当前洪水高度的邻居添加到边缘

就目前而言，对于具有最大海拔 z 的 n x m 阵列，这将具有复杂性 O(nmz)，但通过一些优化我们可以降低到 O(nm)。为此，我们不是只使用一个边缘，每次都从外向内工作，而是使用多个边缘集，每个高度级别一个，并将我们到达的节点放在与其自身相对应的边缘中高度(或当前边缘，如果它们较低)。这样，数组中的每个节点都被添加到边缘和从边缘中删除恰好一次。这是尽可能快的速度。

这是一些代码。我已经用 Python 完成了它，但您应该能够将其转移到 Java——只需假装它是可执行的伪代码即可。您可以添加一个计数器来查看 while 循环的主体确实执行了 24 次，对于此示例，结果为 14。

# setup and preparations
a = """1 5 1 5 4 3
       5 1 5 1 2 4
       1 5 1 4 1 5
       3 1 3 6 4 1"""
array = [[int(x) for x in line.strip().split()] 
         for line in a.strip().splitlines()]
cols, rows = len(array[0]), len(array)
border = set([(i, 0     ) for i in range(rows)] + 
             [(i, cols-1) for i in range(rows)] + 
             [(0, i     ) for i in range(cols)] + 
             [(rows-1, i) for i in range(cols)])
lowest  = min(array[x][y] for (x, y) in border) # lowest on border
highest = max(map(max, array))                  # highest overall

# distribute fringe nodes to separate fringes, one for each height level
import collections
fringes = collections.defaultdict(set) # maps points to sets
for (x, y) in border:
    fringes[array[x][y]].add((x, y))

# 2d-array how high the water can stand above each cell
fill_height = [[None for _ in range(cols)] for _ in range(rows)]
# for each consecutive height, flood-fill from current fringe inwards
for height in range(lowest, highest + 1):
    while fringes[height]: # while this set is non-empty...
        # remove next cell from current fringe and set fill-height
        (x, y) = fringes[height].pop()
        fill_height[x][y] = height
        # put not-yet-flooded neighbors into fringe for their elevation
        for x2, y2 in [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]:
            if 0 <= x2 < rows and 0 <= y2 < cols and fill_height[x2][y2] is None:
                # get fringe for that height, auto-initialize with new set if not present
                fringes[max(height, array[x2][y2])].add((x2, y2))

# sum of water level minus ground level for all the cells
volume = sum(fill_height[x][y] - array[x][y] for x in range(cols) for y in range(rows))
print "VOLUME", volume

要从文件中读取更大的测试用例，请将顶部的 a = """...""" 替换为:

with open("test") as f:
    a = f.read()

文件应该只包含问题中的原始数组，没有维度信息，用空格和换行符分隔。