一个经典算法问题，在2D版本通常被描述为

A classic algorithm question in 2D version is typically described as

给定n个非负整数重新presenting高程地图，每一个栏的宽度为1，计算它多少水是能够捕获雨后。

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

例如，由于输入

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

返回值将是

6

这是我用来解决上述问题的二维算法是

The algorithm that I used to solve the above 2D problem is

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地形的最大值。即要实现

My Question is how to make the above algorithm extensible to the 3D version of the problem, to compute the maximum of water trapped in real-world 3D terrain. i.e. To implement

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

样品图：

我们知道的标高在每个（X，Y）点，目标是计算的水可被截留在形状的最大体积。有什么想法和引用的欢迎。

We know the elevation at each (x, y) point and the goal is to compute the maximum volume of water that can be trapped in the shape. Any thoughts and references are welcome.

推荐答案

有关地形的每一点考虑从该点地形的边界的所有路径。水的水平将是最低的那些路径的点的最大高度。为了找到它，我们需要执行一个稍微修改Dijkstra算法，尽显水位矩阵从边境开始。

For each point on the terrain consider all paths from that point to the border of the terrain. The level of water would be the minimum of the maximum heights of the points of those paths. To find it we need to perform a slightly modified Dijkstra's algorithm, filling the water level matrix starting from the border.

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