被困雨水在三維最大音量

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版本的問題，來計算真實世界三維地形中被困水的最大值。即要實現

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）運行時間。

Answer 3

這個問題非常接近灰度圖像的形態分水嶺（http://en.wikipedia.org/wiki/Watershed_(image_processing)）的構建。

一種方法如下（洪水過程）：

• 排序的所有像素通過增加高度。

• 通過增加高程逐步工作，爲每個流域盆地的像素分配標籤。

• 一個新的高度水平，你需要標記一個新的像素集合：

  • 有些人沒有標記 鄰居，他們形成局部最低配置，並開始一個新的匯水盆地。
  • 有些人只有鄰居有相同的標籤，他們可以被類似地標記（他們擴大了流域）。
  • 一些有不同標籤的鄰居。它們不屬於特定的集水盆地，它們定義了分水嶺線。

您需要提高標準的分水嶺算法能夠計算水的體積。您可以通過確定每個盆地的最大水位並推算每個像素的地面高度。盆地中的水位由其周圍最低分水嶺像素的高程給出。

每當您發現一個分水嶺像素時，您都可以採取行動：如果相鄰盆地尚未分配到一個等級，那麼該盆地可以保持當前水平而不會泄漏。

Answer 4

爲了實現在3D即拍打水的問題，來計算被困雨水最大音量，你可以做這樣的事情：

#include<bits/stdc++.h> 
using namespace std; 

#define MAX 10 

int new2d[MAX][MAX]; 
int dp[MAX][MAX],visited[MAX][MAX]; 


int dx[] = {1,0,-1,0}; 
int dy[] = {0,-1,0,1}; 


int boundedBy(int i,int j,int k,int in11,int in22) 
{ 
    if(i<0 || j<0 || i>=in11 || j>=in22) 
     return 0; 

    if(new2d[i][j]>k) 
     return new2d[i][j]; 

    if(visited[i][j]) return INT_MAX; 

    visited[i][j] = 1; 

    int r = INT_MAX; 
    for(int dir = 0 ; dir<4 ; dir++) 
    { 
     int nx = i + dx[dir]; 
     int ny = j + dy[dir]; 
     r = min(r,boundedBy(nx,ny,k,in11,in22)); 
    } 
    return r; 
} 

void mark(int i,int j,int k,int in1,int in2) 
{ 
    if(i<0 || j<0 || i>=in1 || j>=in2) 
     return; 

    if(new2d[i][j]>=k) 
     return; 

    if(visited[i][j]) return ; 

    visited[i][j] = 1; 

    for(int dir = 0;dir<4;dir++) 
    { 
     int nx = i + dx[dir]; 
     int ny = j + dy[dir]; 
     mark(nx,ny,k,in1,in2); 
    } 
    dp[i][j] = max(dp[i][j],k); 
} 

struct node 
{ 
    int i,j,key; 
    node(int x,int y,int k) 
    { 
     i = x; 
     j = y; 
     key = k; 
    } 
}; 

bool compare(node a,node b) 
{ 
    return a.key>b.key; 
} 
vector<node> store; 

int getData(int input1, int input2, int input3[]) 
{ 

    int row=input1; 
    int col=input2; 
    int temp=0; 
    int count=0; 

     for(int i=0;i<row;i++) 
     { 
      for(int j=0;j<col;j++) 
      { 
       if(count==(col*row)) 
       break; 
      new2d[i][j]=input3[count]; 
      count++; 
      } 
     } 

    store.clear(); 
    for(int i = 0;i<input1;i++) 
     { 
      for(int j = 0;j<input2;j++) 
      { 
       store.push_back(node(i,j,new2d[i][j])); 
      } 
     } 
    memset(dp,0,sizeof(dp)); 

     sort(store.begin(),store.end(),compare); 

     for(int i = 0;i<store.size();i++) 
     { 
      memset(visited,0,sizeof(visited)); 

      int aux = boundedBy(store[i].i,store[i].j,store[i].key,input1,input2); 
      if(aux>store[i].key) 
      { 

       memset(visited,0,sizeof(visited)); 
       mark(store[i].i,store[i].j,aux,input1,input2); 
      } 

     } 

     long long result =0 ; 

     for(int i = 0;i<input1;i++) 
     { 

      for(int j = 0;j<input2;j++) 
      { 
       result = result + max(0,dp[i][j]-new2d[i][j]); 
      } 
     } 

     return result; 

} 


int main() 
{ 
    cin.sync_with_stdio(false); 
    cout.sync_with_stdio(false); 
     int n,m; 
     cin>>n>>m; 
     int inp3[n*m]; 
     store.clear(); 

      for(int j = 0;j<n*m;j++) 
      { 
       cin>>inp3[j]; 

      } 

    int k = getData(n,m,inp3); 
     cout<<k; 

    return 0; 
} 

Answer 5

這個問題可以使用優先權洪水算法來解決。在過去的幾十年裏，它被發現並發表了很多次（其他人也回答了這個問題），儘管你所尋找的特定變體在我的文獻中並不是這樣。

你可以找到算法及其變種here的評論文章。自該論文發表以來，發現了更快的變體（link），以及在數萬億個細胞的數據集上執行此計算的方法（link）。 here討論了選擇性地違反低/窄分界線的方法。如果您想要這些文件的副本，請與我聯繫。

我有一個存儲庫here與許多上述變種;可以找到其他的實現here。

一個簡單的腳本使用RichDEM庫如下計算體積：

#include "richdem/common/version.hpp" 
#include "richdem/common/router.hpp" 
#include "richdem/depressions/Lindsay2016.hpp" 
#include "richdem/common/Array2D.hpp" 

/** 
    @brief Calculates the volume of depressions in a DEM 
    @author Richard Barnes (rbarnes@umn.edu) 

    Priority-Flood starts on the edges of the DEM and then works its way inwards 
    using a priority queue to determine the lowest cell which has a path to the 
    edge. The neighbours of this cell are added to the priority queue if they 
    are higher. If they are lower, then they are members of a depression and the 
    elevation of the flooding minus the elevation of the DEM times the cell area 
    is the flooded volume of the cell. The cell is flooded, total volume 
    tracked, and the neighbors are then added to a "depressions" queue which is 
    used to flood depressions. Cells which are higher than a depression being 
    filled are added to the priority queue. In this way, depressions are filled 
    without incurring the expense of the priority queue. 

    @param[in,out] &elevations A grid of cell elevations 

    @pre 
    1. **elevations** contains the elevations of every cell or a value _NoData_ 
     for cells not part of the DEM. Note that the _NoData_ value is assumed to 
     be a negative number less than any actual data value. 

    @return 
    Returns the total volume of the flooded depressions. 

    @correctness 
    The correctness of this command is determined by inspection. (TODO) 
*/ 
template <class elev_t> 
double improved_priority_flood_volume(const Array2D<elev_t> &elevations){ 
    GridCellZ_pq<elev_t> open; 
    std::queue<GridCellZ<elev_t> > pit; 
    uint64_t processed_cells = 0; 
    uint64_t pitc   = 0; 
    ProgressBar progress; 

    std::cerr<<"\nPriority-Flood (Improved) Volume"<<std::endl; 
    std::cerr<<"\nC Barnes, R., Lehman, C., Mulla, D., 2014. Priority-flood: An optimal depression-filling and watershed-labeling algorithm for digital elevation models. Computers & Geosciences 62, 117–127. doi:10.1016/j.cageo.2013.04.024"<<std::endl; 

    std::cerr<<"p Setting up boolean flood array matrix..."<<std::endl; 
    //Used to keep track of which cells have already been considered 
    Array2D<int8_t> closed(elevations.width(),elevations.height(),false); 

    std::cerr<<"The priority queue will require approximately " 
      <<(elevations.width()*2+elevations.height()*2)*((long)sizeof(GridCellZ<elev_t>))/1024/1024 
      <<"MB of RAM." 
      <<std::endl; 

    std::cerr<<"p Adding cells to the priority queue..."<<std::endl; 

    //Add all cells on the edge of the DEM to the priority queue 
    for(int x=0;x<elevations.width();x++){ 
    open.emplace(x,0,elevations(x,0)); 
    open.emplace(x,elevations.height()-1,elevations(x,elevations.height()-1)); 
    closed(x,0)=true; 
    closed(x,elevations.height()-1)=true; 
    } 
    for(int y=1;y<elevations.height()-1;y++){ 
    open.emplace(0,y,elevations(0,y) ); 
    open.emplace(elevations.width()-1,y,elevations(elevations.width()-1,y)); 
    closed(0,y)=true; 
    closed(elevations.width()-1,y)=true; 
    } 

    double volume = 0; 

    std::cerr<<"p Performing the improved Priority-Flood..."<<std::endl; 
    progress.start(elevations.size()); 
    while(open.size()>0 || pit.size()>0){ 
    GridCellZ<elev_t> c; 
    if(pit.size()>0){ 
     c=pit.front(); 
     pit.pop(); 
    } else { 
     c=open.top(); 
     open.pop(); 
    } 
    processed_cells++; 

    for(int n=1;n<=8;n++){ 
     int nx=c.x+dx[n]; 
     int ny=c.y+dy[n]; 
     if(!elevations.inGrid(nx,ny)) continue; 
     if(closed(nx,ny)) 
     continue; 

     closed(nx,ny)=true; 
     if(elevations(nx,ny)<=c.z){ 
     if(elevations(nx,ny)<c.z){ 
      ++pitc; 
      volume += (c.z-elevations(nx,ny))*std::abs(elevations.getCellArea()); 
     } 
     pit.emplace(nx,ny,c.z); 
     } else 
     open.emplace(nx,ny,elevations(nx,ny)); 
    } 
    progress.update(processed_cells); 
    } 
    std::cerr<<"t Succeeded in "<<std::fixed<<std::setprecision(1)<<progress.stop()<<" s"<<std::endl; 
    std::cerr<<"m Cells processed = "<<processed_cells<<std::endl; 
    std::cerr<<"m Cells in pits = " <<pitc   <<std::endl; 

    return volume; 
} 

template<class T> 
int PerformAlgorithm(std::string analysis, Array2D<T> elevations){ 
    elevations.loadData(); 

    std::cout<<"Volume: "<<improved_priority_flood_volume(elevations)<<std::endl; 

    return 0; 
} 

int main(int argc, char **argv){ 
    std::string analysis = PrintRichdemHeader(argc,argv); 

    if(argc!=2){ 
    std::cerr<<argv[0]<<" <Input>"<<std::endl; 
    return -1; 
    } 

    return PerformAlgorithm(argv[1],analysis); 
} 

它應該是直着這個適應任何二維數組格式使用的是

僞代碼中，以下是等效於前述：

Let PQ be a priority-queue which always pops the cell of lowest elevation 
Let Closed be a boolean array initially set to False 
Let Volume = 0 
Add all the border cells to PQ. 
For each border cell, set the cell's entry in Closed to True. 
While PQ is not empty: 
    Select the top cell from PQ, call it C. 
    Pop the top cell from PQ. 
    For each neighbor N of C: 
    If Closed(N): 
     Continue 
    If Elevation(N)<Elevation(C): 
     Volume += (Elevation(C)-Elevation(N))*Area 
     Add N to PQ, but with Elevation(C) 
    Else: 
     Add N to PQ with Elevation(N) 
    Set Closed(N)=True 

Answer 6

這裏是各項─

0的簡單代碼

#include<iostream> 
using namespace std; 
int main() 
{ 
    int n,count=0,a[100]; 
    cin>>n; 
    for(int i=0;i<n;i++) 
    { 
     cin>>a[i]; 
    } 
    for(int i=1;i<n-1;i++) 
    { 
     ///computing left most largest and Right most largest element of array; 
     int leftmax=0; 
     int rightmax=0; 
     ///left most largest 
     for(int j=i-1;j>=1;j--) 
     { 
      if(a[j]>leftmax) 
      { 
       leftmax=a[j]; 
      } 
     } 
     ///rightmost largest 

     for(int k=i+1;k<=n-1;k++) 
     { 
      if(a[k]>rightmax) 
      { 
       rightmax=a[k]; 
      } 
     } 
     ///computing hight of the water contained- 

     int x=(min(rightmax,leftmax)-a[i]); 
     if(x>0) 
     { 
      count=count+x; 
     } 

    } 
    cout<<count; 
    return 0; 
}