3D中被困雨水的最大容积

Question

2D版本中的经典算法问题通常被描述为

给定n个非负整数表示每个柱的宽度为1的高程图,计算下雨后能够捕获的水量.

例如,给定输入

[0,1,0,2,1,0,1,3,2,1,2,1] 

返回值是

6

我用来解决上述2D问题的算法是

int trapWaterVolume2D(vector<int> A) {
    int n = A.size();
    vector<int> leftmost(n, 0), rightmost(n, 0);

    //left exclusive scan, O(n), the highest bar to the left each point
    int leftMaxSoFar = 0;
    for (int i = 0; i < n; i++){
        leftmost[i] = leftMaxSoFar;
        if (A[i] > leftMaxSoFar) leftMaxSoFar = A[i];
    }


    //right exclusive scan, O(n), the highest bar to the right each point
    int rightMaxSoFar = 0;
    for (int i = n - 1; i >= 0; i--){
        rightmost[i] = rightMaxSoFar;
        if (A[i] > rightMaxSoFar) rightMaxSoFar = A[i];
    }

    // Summation, O(n)
    int vol = 0;
    for (int i = 0; i < n; i++){
        vol += max(0, min(leftmost[i], rightmost[i]) - A[i]);
    }
    return vol;
}

我的问题是如何使上述算法可扩展到问题的3D版本,以计算在真实世界3D地形中捕获的最大水量.即实施

int trapWaterVolume3D(vector<vector<int> > A);

示例图:

我们知道每个(x,y)点的高程,目标是计算可以在形状中捕获的最大水量.欢迎任何想法和参考.

Answer 1

对于地形上的每个点,考虑从该点到地形边界的所有路径.水位将是这些路径点的最大高度的最小值.为了找到它,我们需要执行略微修改的Dijkstra算法,从边界开始填充水位矩阵.

For every point on the border set the water level to the point height
For every point not on the border set the water level to infinity
Put every point on the border into the set of active points
While the set of active points is not empty:
    Select the active point P with minimum level
    Remove P from the set of active points
    For every point Q adjacent to P:
        Level(Q) = max(Height(Q), min(Level(Q), Level(P)))
        If Level(Q) was changed:
            Add Q to the set of active points

Answer 2

user3290797 的“稍微修改的 Dijkstra 算法”比 Dijkstra 的算法更接近 Prim 的算法。在最小生成树术语中，我们准备一个图，每个图块一个顶点，一个顶点用于外部，边的权重等于它们两个相邻图块的最大高度（外部高度为“负无穷大”）。

给定此图中到外部顶点的路径，路径中边的最大权重是水沿该路径逃逸必须达到的高度。最小生成树的相关属性是，对于每对顶点，生成树中路径中的边的最大权重是这些顶点之间的所有路径中可能的最小值。因此，最小生成树描述了最经济的水逃逸路径，并且可以通过一次遍历在线性时间内提取水高。

作为奖励，由于该图是平面图，因此有一种用于计算最小生成树的线性时间算法，由交替的 Boruvka 传递和简化组成。这改进了 Prim 的 O(n log n) 运行时间。