3D 中截留雨水的最大体积 [英] The Maximum Volume of Trapped Rain Water in 3D

查看:18
本文介绍了3D 中截留雨水的最大体积的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

二维版本的经典算法问题通常被描述为

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

给定 n 个非负整数表示高程图,其中每个条的宽度为 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

这篇关于3D 中截留雨水的最大体积的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆