一个二维数组的水容量

Question

我需要在大学里完成一个小练习，但是我已经卡了一段时间了。这个练习是关于计算2D数组的水容量，用户需要输入2D数组的宽度（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

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

但由于我的解决方案不够快，我正在寻找更高效的解决方案。以下代码是其中神奇部分：

    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上提供了相同的练习。然而，我测试了许多解决方案，其中一些实际上通过了我的前四个测试用例，但大多数在简单的测试用例上已经失败。Talent Buddy在制作测试用例方面做得很差：实际上他们只有两个测试用例。如果您想查看他们的解决方案，只需注册并输入此代码（语言为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的解决方案是可行的，但像我的解决方案一样，它不足以通过更大的输入测试用例，有没有更有效的实现方法？

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

- Chantal

---

一个数组什么时候可以装水了？ - moffeltje

不是的，我不明白为什么第一个例子输出8。 - moffeltje

我也不清楚如何计算“水量”。除了解决数组的答案之外，计算该值的公式还可以帮助重新构思问题。 - Surreal Dreams

@moffeltje，"罐子"的边缘高度为"元素"。中心高度为两个"元素"。因此，您可以加入8单位的水，直到罐子溢出。将数字视为罐子的第三维或类似物。 - Tom

我认为你可以使用一种重复的泛洪填充方法。从数组中的最小值到最大值，对所有数字进行重复操作：从边界开始，填充所有低于或等于当前数字的单元格，并且对于每个在该轮中首先到达的单元格，记忆该数字。这就是该单元格中水位的高度。然后只需从这些数字中减去原始数字即可。具有最高数字K的NxN数组的复杂度应为O(K*N^2)，可能通过一些优化为O(N^2)。不确定这是否比你的更好或更差。 - tobias_k

Answer 1

这是我的解决方案。其思路如下：您需要反复使用不断增加的“海平面”来洪水填充数组。节点首次被淹没的高度将是该节点在“洪水”退去时所保留水池的相同高度。

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

目前情况下，对于一个最大高程为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()

文件应该只包含原始数组，不包括维度信息，用空格和换行符分隔。

- tobias_k

---

我不明白为什么这会起作用。而且我不明白为什么你要从最低点开始到最高点，这样你就需要做更多的赋值（我想）。另外，你对边界做了什么？你不能填充它们的邻居。我从未在Python中做过任何事情，但我编译了你的代码并在一些测试案例上进行了测试，小的测试案例可以工作。但是更大的测试案例需要太长时间来复制到你的数组a中。我不知道如何使用Python读取文件，也许你可以实现它从文本文件中读取吗？然后我可以测试你的代码是否比我的快。 - Chantal

你的代码在大测试案例中运行良好。将其复制到Xcode时崩溃了，但是使用文本编辑器可以正常工作，因此我能够在不读取文件的情况下进行测试。现在我只是试图理解你的代码，基本上你每次都有一组(x,y)，其中每个高度用作数组的索引（直接寻址表）？并且使用fill height时，你只是将一个集合用作索引，我不认为这在Java中是可能的哈哈。我想我会在Java中创建一个对象。 - Chantal

我会用Java编写代码，希望它足以通过我的老师设置的隐藏测试用例，感谢你的解决方案！我会保持更新。 - Chantal

我认为你错了，你的while循环fringes[height]的复杂度是O(nm)，即矩阵的大小，但是从最低到最高包围该循环的循环并不会使这个算法的复杂度变成O(nm)，而是变成了O(n^2)。顺便说一下，看看我们之前的聊天记录吧。 - Chantal

@Chantal我找到了瓶颈。将哈希映射替换为简单的2D整数数组后，执行时间急剧下降，特别是在Java中。即使哈希映射应该具有O（1）查找、更新等功能，仍然存在一些开销，例如用于检查相等性等。 - tobias_k

Answer 2

talentbuddy.co有一个编程任务叫做rain。如果你注册了一个账户，你就可以查看其他人的解决方案。

#include <iostream>
#include <vector>

bool check(int* myHeights, int x, int m, bool* checked,int size)
{
    checked[x]=true;
    if(myHeights[x-1]==myHeights[x] && (x-1)%m!=0 && !checked[x-1])
    {
        if(!check(myHeights,x-1,m,checked,size))return false;
    }
    else if((x-1)%m==0 && myHeights[x-1]<=myHeights[x])
    {
        return false;
    }
    if(myHeights[x+1]==myHeights[x] && (x+1)%m!=m-1 && !checked[x+1])
    {
        if(!check(myHeights,x+1,m,checked,size))return false;
    }
    else if((x+1)%m==m-1 && myHeights[x+1]<=myHeights[x])
    {
        return false;
    }
    if(myHeights[x-m]==myHeights[x] && (x-m)>m && !checked[x-m])
    {
        if(!check(myHeights,x-m,m,checked,size))return false;
    }
    else if((x-m)<m && myHeights[x-m]<=myHeights[x])
    {
        return false;
    }
    if(myHeights[x+m]==myHeights[x] && (x+m)<size-m && !checked[x+m])
    {
        if(!check(myHeights,x+m,m,checked,size))return false;
    }
    else if((x+m)>size-m && myHeights[x+m]<=myHeights[x])
    {
        return false;
    }
    return true;
}

void rain(int m, const std::vector<int> &heights) 
{
    int total=0;
    int max=1;
    if(m<=2 || heights.size()/m<=2)
    {
        std::cout << total << std::endl;
        return;
    }
    else
    {
        int myHeights[heights.size()];
        for(int x=0;x<heights.size();++x)
        {
            myHeights[x]=heights[x];
        }
        bool done=false;
        while(!done)
        {
            done=true;
            for(int x=m+1;x<heights.size()-m;++x)
            {
                if(x<=m || x%m==0 || x%m==m-1)
                {
                    continue;
                }

                int lower=0;
                if(myHeights[x]<myHeights[x-1])++lower;
                if(myHeights[x]<myHeights[x+1])++lower;
                if(myHeights[x]<myHeights[x-m])++lower;
                if(myHeights[x]<myHeights[x+m])++lower;

                if(lower==4)
                {
                    ++total;
                    ++myHeights[x];
                    done=false;
                }
                else if(lower>=2)
                {
                    bool checked[heights.size()];
                    for(int y=0;y<heights.size();++y)
                    {
                        checked[y]=false;
                    }
                    if(check(myHeights,x,m,checked,heights.size()))
                    {
                        ++total;
                        ++myHeights[x];
                        done=false;
                    }
                }
            }
        }
    }
    std::cout << total << std::endl;
    return;
}

- dufresnb

---

注意：这不是Java，但原理是相同的（我并没有查看代码以确保准确性）。 - Russell Uhl

我发现详细解释答案并不如让他们自己翻译逻辑有帮助 :) - dufresnb

我同意。我只是想确保原帖作者没有复制粘贴并想知道为什么什么都不起作用。 - Russell Uhl

谢谢，我会尽快试一下并告诉你！还有，Russell，我可不傻哈哈。 - Chantal

所有这些代码都不起作用，它们都适用于简单的测试用例，但对于复杂的测试用例则无法胜任。看到人们发送的代码实际上通过了测试用例，这让人感到不安。同时，看到Talent Buddy有如此糟糕的测试用例也让人不安。无论如何，我还是没有进展，我的代码仍然是目前最好的。 - Chantal