在3d棋盘中找到水量的提示 [英] Tips on finding the volume of water in a 3d chess board

问题描述

所以我有一个任务，我必须重新创建一个3d棋盘，这是一个RxC网格的正方形，每个都是不同的高度。如果棋盘是水密的，有人在它上面浇水，直到它不再能容纳水，它将持有固定量的水。如果板已经保持其最大体积的水，任何过量的水倒在板上将从边缘排出，没有高容器包围板。你可以假设棋盘上的正方形是一平方英寸，高度以英寸给出。

  int CalcContainedWater（const int * p_data，int num_columns，int num_rows）
  / pre> 
 
 
其中 p_data 是指向连续二维，行主数组的第一个元素的指针的有符号整数。 
 
 
 
请记住 p_data中的值，以确保它的正确性。 
 
 
 
例如：
 
 
 
 A）下面的板子产生了3的容量。
  1，1，1，1，1，
 1，0，0，0，1，
 1，1，1，1，1，
  
 B）以下板块产生0的控制。
  1，0，1，
 1， 0，1，
 1，1，1，
  
 
 
 <遏制1次。
  0，1，0，
 1，0，1，
 0， 1，0，
  
 这是我到目前为止： p> 
 
 
  #includestdafx.h
 #include< queue> 
 #include< vector> 
 using namespace std; 
 
枚举GridPosition 
 {
 TOP_LEFT_CORNER，
 TOP_RIGHT_CORNER，
 BOTTOM_LEFT_CORNER，
 BOTTOM_RIGHT_CORNER，
 TOP_ROW，
 BOTTOM_ROW ，
 LEFT_COLUMN，
 RIGHT_COLUMN，
 FREE，
}; 
 
 struct Square 
 {
 int nHeight; 
 int nPos; 
 GridPosition gPos; 
 bool bIsVisited; 
 bool bIsFenced; 
 bool bIsFlooding; 
 
 Square（）{nHeight = 0; nPos = 0; gPos = FREE; bIsVisited = false; bIsFenced = false; bIsFlooding = false;}; 
〜Square（）{}; 
 Square（int Height，int Pos，GridPosition GridPos，bool Visited，bool Fenced，bool Flooding）
 {
 nHeight = Height; 
 nPos = Pos; 
 gPos = GridPos; 
 bIsVisited =访问; 
 bIsFenced =围栏
 bIsFlooding =洪水; 
} 
}; 
 
 template< typename FirstType，typename SecondType> 
 struct PairComparator 
 {
 bool operator（）（const pair< FirstType，SecondType>& p1，
 const pair< FirstType，SecondType>& p2）const 
 {
 return p1.second> p2.second; 
} 
}; 
 
 int CalcContainedWater（const int * p_data，int num_columns，int num_rows）; 
 
 int CalcContainedWater（const int * p_data，int num_columns，int num_rows）
 {
 priority_queue< pair< int，int> ;, vector< int，int& ，PairComparator< int，int>> qPerimeter; 
 queue< pair< int，int>> qFlooding; 
 vector< Square> vSquareVec（num_columns * num_rows）; 
 
 int nTotalContaininged = 0; 
 
 int nCurrentSqHeight = 0; 
 int nCurrWaterLvl = 0; 
 int nDepth = 1; 
 
 for（int nRow = 0; nRow< num_rows; ++ nRow）
 {
 for（int nColumn = 0; nColumn< num_columns; ++ nColumn）
 {
 int nCurrArrayPoint = nRow * num_columns + nColumn; 
 nCurrentSqHeight = p_data [nCurrArrayPoint]; 
 
 Square sSquare（nCurrentSqHeight，nCurrArrayPoint，FREE，false，false，false）; 
 
 if（nRow == 0& nColumn == 0）
 sSquare.gPos = TOP_LEFT_CORNER; 
 else if（nRow == 0& nColumn == num_columns  -  1）
 sSquare.gPos = TOP_RIGHT_CORNER; 
 else if（nRow == num_rows  -  1& nColumn == 0）
 sSquare.gPos = BOTTOM_LEFT_CORNER; 
 else if（nRow == num_rows  -  1& ncolumn == num_columns  -  1）
 sSquare.gPos = BOTTOM_RIGHT_CORNER; 
 else if（nRow == 0）
 sSquare.gPos = TOP_ROW; 
 else if（nRow == num_rows -1）
 sSquare.gPos = BOTTOM_ROW; 
 else if（nColumn == 0）
 sSquare.gPos = LEFT_COLUMN; 
 else if（nColumn == num_columns  -  1）
 sSquare.gPos = RIGHT_COLUMN; 
 
 vSquareVec [nCurrArrayPoint] = sSquare; 
 
 if（nRow == 0 || nColumn == 0 || 
 nColumn == num_columns  -  1 || nRow == num_rows -1）
 {
 sSquare.bIsFenced = true; 
 
 vSquareVec [nCurrArrayPoint] = sSquare; 
 
 pair< int，int> p1（nCurrArrayPoint，nCurrentSqHeight）; 
 
 qPerimeter.push（p1）; 
} 
} 
} 
 
 nCurrWaterLvl = qPerimeter.top（）。 
 
 while（！qPerimeter.empty（））
 {
 pair< int，int& PerimPos = qPerimeter.top（）; 
 qPerimeter.pop（）; 
 
 if（！vSquareVec [PerimPos.first] .bIsVisited）
 {
 if（vSquareVec [PerimPos.first] .nHeight> nCurrWaterLvl）
 nCurrWaterLvl = vSquareVec [PerimPos.first] .nHeight; 
 
 vSquareVec [PerimPos.first] .bIsFlooding = true; 
 qFlooding.push（PerimPos）; 
 
 while（！qFlooding.empty（））
 {
 pair< int，int& FloodPos = qFlooding.front（）; 
 qFlooding.pop（）; 
 nDepth = nCurrWaterLvl  -  vSquareVec [FloodPos.first] .nHeight; 
 
 if（nDepth> = 0）
 {
 vSquareVec [FloodPos.first] .bIsVisited = true; 
 pair< int，int> newFloodPos; 
 switch（vSquareVec [FloodPos.first] .gPos）
 {
 case TOP_LEFT_CORNER：
 if（！vSquareVec [FloodPos.first + 1] .bIsVisited&& 
！vSquareVec [FloodPos.first + 1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + 1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + 1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + 1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first + num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first + num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + num_rows] .nHeight; 
 qFrooding.push（newFloodPos）; 
} 
 break; 
 case TOP_RIGHT_CORNER：
 if（！vSquareVec [FloodPos.first-1] .bIsVisited& 
！vSquareVec [FloodPos.first-1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first  -  1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first  -  1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first  -  1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first + num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first + num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 break; 
 case BOTTOM_LEFT_CORNER：
 if（！vSquareVec [FloodPos.first + 1] .bIsVisited& 
！vSquareVec [FloodPos.first + 1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + 1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + 1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + 1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first-num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first-num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first-num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first-num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first-num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 break; 
 case BOTTOM_RIGHT_CORNER：
 if（！vSquareVec [FloodPos.first-1] .bIsVisited&& 
！vSquareVec [FloodPos.first_1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first  -  1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first  -  1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first  -  1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first-num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first-num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first-num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first-num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first-num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 break; 
 case TOP_ROW：
 if（！vSquareVec [FloodPos.first-1] .bIsVisited& 
！vSquareVec [FloodPos.first-1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first  -  1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first  -  1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first  -  1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first + 1] .bIsVisited& 
！vSquareVec [FloodPos.first + 1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + 1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + 1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + 1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first + num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first + num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 break; 
 case BOTTOM_ROW：
 if（！vSquareVec [FloodPos.first-1] .bIsVisited&& 
！vSquareVec [FloodPos.first_1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first  -  1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first  -  1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first  -  1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first + 1] .bIsVisited&& 
！vSquareVec [FloodPos.first + 1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + 1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + 1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + 1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first-num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first-num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first-num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first-num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first-num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 break; 
 case LEFT_COLUMN：
 if（！vSquareVec [FloodPos.first + 1] .bIsVisited& 
！vSquareVec [FloodPos.first + 1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + 1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + 1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + 1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first + num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first + num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first-num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first-num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first-num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first-num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first-num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 break; 
 case RIGHT_COLUMN：
 if（！vSquareVec [FloodPos.first-1] .bIsVisited&& 
！vSquareVec [FloodPos.first-1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first  -  1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first  -  1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first  -  1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first + num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first + num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first-num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first-num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first-num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first-num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first-num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 break; 
 case FREE：
 if（！vSquareVec [FloodPos.first + 1] .bIsVisited& 
！vSquareVec [FloodPos.first + 1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + 1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + 1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + 1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first  -  1] .bIsVisited&& 
！vSquareVec [FloodPos.first-1] .bIsFlooding）
 {
 vSquareVec [FloodPos.first  -  1] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first  -  1] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first  -  1] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first + num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first + num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first + num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first + num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first + num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 if（！vSquareVec [FloodPos.first-num_rows] .bIsVisited&& 
！vSquareVec [FloodPos.first-num_rows] .bIsFlooding）
 {
 vSquareVec [FloodPos.first-num_rows] .bIsFlooding = true; 
 newFloodPos.first = vSquareVec [FloodPos.first-num_rows] .nPos; 
 newFloodPos.second = vSquareVec [FloodPos.first-num_rows] .nHeight; 
 qFlooding.push（newFloodPos）; 
} 
 
 nTotalContained + = nDepth; 
 
 break; 
} 
 
} 
 else 
 {
 vSquareVec [FloodPos.first] .bIsFlooding = false; 
 if（！vSquareVec [FloodPos.first] .bIsFenced）
 {
 vSquareVec [FloodPos.first] .bIsFenced = true; 
 qPerimeter.push（FloodPos）; 
} 
} 
 
} 
} 
 
} 
 return nTotalContained; 
} 
  
 
 
所有我发现的是顶部，底部， 。
 
 
 
目前，我一直在努力弄清楚如何获得总体积，知道如果水的高度较小，水会溢出到正方形。我看的越多，我认为应该递归，但是找不到一种方法来实现它。
 
 
 
任何帮助将非常感激。不寻找答案只是一个推进正确的方向，我需要做的。 
解决方案
有趣的问题，有许多不同的解决方案。我一直在想，今天下午，我会去像洪水填充一个优先级队列（min-heap，或许）。让我们将它称为 fence 。
 
 
 
您还需要跟踪哪些项目已访问。 
 
 
 
将网格周边的所有点添加到篱笆 
 
 
 
现在你这样循环：
 
 
 
从 fence 。您已选择周边最低点之一。
 
 
 
 
 
如果该项目已访问，请舍弃它并再次循环。
 
 
如果没有访问，它的高度只有当它大于当前水位时才会成为新的水位。
 
 
 
 
 
你现在从这一点做一个洪水填充。你可以递归（深度优先），但我将使用无序队列（广度优先）讨论这个问题。让我们将这个队列称为 flood 。您首先将项目推送到 flood 。
 
 
 
 Flooding则会这样：循环，直到没有项目 flood  ... 
 
 
 
 
 
从洪水 
 
 
如果已经访问，请忽略它并重新循环。
 
 
如果项目高度小于或等于当前水位，计算高度差并将其添加到总体积中。将项目标记为已访问，然后将所有未访问的邻居添加到 flood 。
 
 
如果项目高度大于当前水位，只需将它添加到 fence 。你需要有一个方法来判断该项目是否已经在 fence   - 你不想再添加它。也许你可以扩展你的访问标志来应对这个问题。
 
 
 
 
 
就是这样。当然，这只是一个思想实验，而我躺在周围的感觉饥饿和seedy，但我认为这是好的。
 
 
 
 
 
 
请求...一些伪代码。
 
 
 
初始设置：
  ＃清除标志。注意我为地图中的每个项目添加了一个'flooding'标志
。item.visited<  -  false＃true表示项目已经添加了水深
 item.fenced< false＃true表示项目在fence队列中
 item.flooding<  -  false＃true表示项目在洪泛队列中
 end 
 
 ##设置外围
为地图边缘上的每个项目（上，左，右，下）
将项目推到篱笆上
 end 
 
水平<  -  0 
 total< ;  -  0 
  
现在算法的主块
 而fence有项目
 item<  -  pop项目从fence 
如果item.visited = true然后再循环
 
 ##更新水位
如果item.height> waterlevel then waterlevel = item.height 
 
 ##使用当前水位的洪水填充项
将项目推送到洪水
 item.flooding<  -  true 
 
 while flood has items 
 item<  -  pop item from flood 
 depth<  -  waterlevel  -  item.height 
 
如果depth> = 0 then 
 ＃项目等于或低于水位。将其深度添加到总计。 
 total<  -  total + depth 
 item.visited<  -  true 
 
＃考虑项目的所有直接邻居。 
 
的每个邻居if nighbour.visited = false then 
如果neighbour.flooding = false then 
将邻居推送到洪水
 neighbour.flooding < -  true 
 end 
 end 
 end 
 else 
＃项目高于水
 item.flooding<  -  false 
如果item.fenced = false然后
将项目推送到fence上
 item.fenced<  -  true 
 end 
 end 
 
 end 
 end 
  
 
So I have an assignment where I have to recreate a 3d chessboard that is a RxC grid of squares each being a different height. If the chessboard is water tight, and someone pours water all over it until it can hold no more water, it will hold a fixed amount of water. If the board is already holding its maximum volume of water, any excess water poured onto the board will drain off the edges, there is no tall container surrounding the board. You can assume the squares on the chess board are one inch square, and the heights are given in inches. 
int CalcContainedWater( const int *p_data, int num_columns, int num_rows )
Where p_data is a pointer to the first element of a contiguous two-dimensional, row-major array of signed integers. Your function will be tested against a reference implementation for boards of varying shapes and contents to determine its correctness.


Keep in mind the value inside of p_data can hold both positive and negative values for the heights.

For example:

A)  The following board yields a containment of 3.
1, 1, 1, 1, 1,
1, 0, 0, 0, 1,
1, 1, 1, 1, 1,
B) The following board yields a containment of 0.
1, 0, 1,
1, 0, 1,
1, 1, 1,
C) The following board yields a containment of 1.
0, 1, 0,
1, 0, 1,
0, 1, 0,
This is what I have so far :
    #include "stdafx.h"
    #include <queue>
    #include <vector>
    using namespace std;

enum GridPosition
{
    TOP_LEFT_CORNER,
    TOP_RIGHT_CORNER,
    BOTTOM_LEFT_CORNER,
    BOTTOM_RIGHT_CORNER,
    TOP_ROW,
    BOTTOM_ROW,
    LEFT_COLUMN,
    RIGHT_COLUMN,
    FREE,
};

struct Square
{
    int nHeight;
    int nPos;
    GridPosition gPos;
    bool bIsVisited;
    bool bIsFenced;
    bool bIsFlooding;

    Square(){ nHeight = 0; nPos = 0; gPos = FREE; bIsVisited = false; bIsFenced = false; bIsFlooding = false;};
    ~Square(){};
    Square( int Height, int Pos, GridPosition GridPos, bool Visited, bool Fenced, bool Flooding) 
    { 
        nHeight = Height;
        nPos = Pos;
        gPos = GridPos;
        bIsVisited = Visited;
        bIsFenced = Fenced;
        bIsFlooding = Flooding;
    }
};

template< typename FirstType, typename SecondType >
struct PairComparator 
{
  bool operator()( const pair<FirstType, SecondType>& p1,
    const pair<FirstType, SecondType>& p2 ) const 
    {  
        return p1.second > p2.second;
    }
};

int CalcContainedWater( const int *p_data, int num_columns, int num_rows );

int CalcContainedWater( const int *p_data, int num_columns, int num_rows )
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, PairComparator<int,int>> qPerimeter;
    queue<pair<int,int>> qFlooding;
    vector<Square> vSquareVec(num_columns * num_rows);

    int nTotalContained = 0;

    int nCurrentSqHeight = 0;
    int nCurrWaterLvl = 0;
    int nDepth = 1;

    for( int nRow = 0; nRow < num_rows; ++nRow)
    {
        for( int nColumn = 0; nColumn < num_columns; ++ nColumn)
        {
            int nCurrArrayPoint = nRow * num_columns + nColumn;
            nCurrentSqHeight = p_data[nCurrArrayPoint];

            Square sSquare(nCurrentSqHeight, nCurrArrayPoint, FREE, false,false,false);

            if(nRow == 0  && nColumn == 0)
                sSquare.gPos = TOP_LEFT_CORNER;
            else if(nRow == 0  && nColumn == num_columns - 1)
                sSquare.gPos = TOP_RIGHT_CORNER;
            else if(nRow == num_rows - 1  && nColumn == 0)
                sSquare.gPos = BOTTOM_LEFT_CORNER;
            else if(nRow == num_rows - 1  && nColumn == num_columns - 1)
                sSquare.gPos = BOTTOM_RIGHT_CORNER;
            else if( nRow == 0)
                sSquare.gPos = TOP_ROW;
            else if( nRow == num_rows -1 )
                sSquare.gPos = BOTTOM_ROW;
            else if( nColumn == 0)
                sSquare.gPos = LEFT_COLUMN;
            else if( nColumn == num_columns - 1)
                sSquare.gPos = RIGHT_COLUMN;

            vSquareVec[nCurrArrayPoint] = sSquare;

            if( nRow == 0  || nColumn == 0 ||  
                nColumn == num_columns - 1 || nRow == num_rows -1 )
            {
                sSquare.bIsFenced = true;

                vSquareVec[nCurrArrayPoint] = sSquare;

                pair<int,int> p1(nCurrArrayPoint, nCurrentSqHeight);

                qPerimeter.push(p1);
            }
        }
    }

    nCurrWaterLvl = qPerimeter.top().second;

    while( !qPerimeter.empty() )
    {
        pair<int,int> PerimPos = qPerimeter.top();
        qPerimeter.pop();

        if( !vSquareVec[PerimPos.first].bIsVisited )
        {
            if( vSquareVec[PerimPos.first].nHeight > nCurrWaterLvl )
                nCurrWaterLvl = vSquareVec[PerimPos.first].nHeight;

            vSquareVec[PerimPos.first].bIsFlooding = true;
            qFlooding.push(PerimPos);

            while( !qFlooding.empty() )
            {
                pair<int,int> FloodPos = qFlooding.front();
                qFlooding.pop();
                nDepth = nCurrWaterLvl - vSquareVec[FloodPos.first].nHeight;

                if( nDepth >= 0)
                {
                    vSquareVec[FloodPos.first].bIsVisited = true;
                    pair<int,int> newFloodPos;
                    switch(vSquareVec[FloodPos.first].gPos)
                    {
                    case TOP_LEFT_CORNER:
                        if( !vSquareVec[FloodPos.first + 1].bIsVisited && 
                            !vSquareVec[FloodPos.first + 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first + num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first + num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        break;
                    case TOP_RIGHT_CORNER:
                        if( !vSquareVec[FloodPos.first - 1].bIsVisited && 
                            !vSquareVec[FloodPos.first - 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first + num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first + num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        break;
                    case BOTTOM_LEFT_CORNER:
                        if( !vSquareVec[FloodPos.first + 1].bIsVisited && 
                            !vSquareVec[FloodPos.first + 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first - num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first - num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        break;
                    case BOTTOM_RIGHT_CORNER:
                        if( !vSquareVec[FloodPos.first - 1].bIsVisited && 
                            !vSquareVec[FloodPos.first - 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first - num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first - num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        break;
                    case TOP_ROW:
                        if( !vSquareVec[FloodPos.first - 1].bIsVisited && 
                            !vSquareVec[FloodPos.first - 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first + 1].bIsVisited && 
                            !vSquareVec[FloodPos.first + 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first + num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first + num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        break;
                    case BOTTOM_ROW:
                        if( !vSquareVec[FloodPos.first - 1].bIsVisited && 
                            !vSquareVec[FloodPos.first - 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first + 1].bIsVisited && 
                            !vSquareVec[FloodPos.first + 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first - num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first - num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        break;
                    case LEFT_COLUMN:
                        if( !vSquareVec[FloodPos.first + 1].bIsVisited && 
                            !vSquareVec[FloodPos.first + 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first + num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first + num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first - num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first - num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        break;
                    case RIGHT_COLUMN:
                        if( !vSquareVec[FloodPos.first - 1].bIsVisited && 
                            !vSquareVec[FloodPos.first - 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - 1 ].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first + num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first + num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first - num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first - num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        break;
                    case FREE:
                        if( !vSquareVec[FloodPos.first + 1].bIsVisited && 
                            !vSquareVec[FloodPos.first + 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first - 1].bIsVisited && 
                            !vSquareVec[FloodPos.first - 1].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - 1].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - 1].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - 1].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first + num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first + num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first + num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first + num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first + num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }
                        if( !vSquareVec[FloodPos.first - num_rows].bIsVisited && 
                            !vSquareVec[FloodPos.first - num_rows].bIsFlooding)
                        {
                            vSquareVec[FloodPos.first - num_rows].bIsFlooding = true;
                            newFloodPos.first = vSquareVec[FloodPos.first - num_rows].nPos;
                            newFloodPos.second = vSquareVec[FloodPos.first - num_rows].nHeight;
                            qFlooding.push(newFloodPos);
                        }

                        nTotalContained += nDepth;

                        break;
                    }

                }
                else
                {
                    vSquareVec[FloodPos.first].bIsFlooding = false;
                    if( !vSquareVec[FloodPos.first].bIsFenced )
                    {
                        vSquareVec[FloodPos.first].bIsFenced = true;
                        qPerimeter.push(FloodPos);
                    }
                }

            }
        }

    }
    return nTotalContained;
    }
All I'm finding is the top,bottom, left and right square heights.

Currently I'm stuck trying to figure out out how to get the total volume knowing that water will spill over to squares if they are smaller in height. The more that I look at this the more I think that it should be done recursively but can't find a way to implement it.

Any help would be much appreciated. Not looking for the answer just for a push into the right direction into what I need to do. 
解决方案
Fun question, with many varied solutions.  I've been thinking about it this afternoon and I would go for something like flood-fill with a priority queue (min-heap, perhaps).  Let's call it the fence.

You'll also want to keep track of which items have been visited.  Mark all items as unvisited, initially.

Start off by adding all points around the perimeter of your grid to the fence.

Now you loop like so:

Pop the front item from the fence.  You have selected one of the lowest points on the perimeter.


If the item has been visited, discard it and loop again.
If it's unvisited, its height becomes your new water level only if it is greater than the current water level.


You now do a flood-fill from that point.  You can do this recursively (depth-first), but I will discuss this using an unordered queue (breadth-first).  Let's call this queue the flood.  You start by pushing the item onto flood.

Flooding then goes like this:  Loop until there are no items remaining in flood...


Pop an item from flood
If it is already visited, ignore it and loop again.
If the item height is less than or equal to the current water level, compute the height difference and add that to your total volume.  Mark the item as visited, then add all unvisited neighbours to flood.
If the item height is greater than the current water level, just add it to fence.  You'll want to have a way to tell whether the item is already in fence - you don't want to add it again.  Maybe you can extend your 'visited' flags to cope with this.


And that's it.  Admittedly it was just a thought experiment while I lay around feeling hungover and seedy, but I reckon it's good.



As you requested...  Some pseudocode.

Initial setup:
## Clear flags.  Note I've added a 'flooding' flag
for each item in map
    item.visited <- false     # true means item has had its water depth added
    item.fenced <- false      # true means item is in the fence queue
    item.flooding <- false    # true means item is in the flooding queue
end

## Set up perimeter
for each item on edge of map (top, left, right, bottom)
    push item onto fence
end

waterlevel <- 0
total <- 0
Now the main chunk of the algorithm
while fence has items
    item <- pop item from fence
    if item.visited = true then loop again

    ## Update water level
    if item.height > waterlevel then waterlevel = item.height

    ## Flood-fill item using current water level
    push item onto flood
    item.flooding <- true

    while flood has items
        item <- pop item from flood
        depth <- waterlevel - item.height

        if depth >= 0 then
            # Item is at or below water level.  Add its depth to total.
            total <- total + depth
            item.visited <- true

            # Consider all immediate neighbours of item.
            for each neighbour of item
                if neighbour.visited = false then
                    if neighbour.flooding = false then
                        push neighbour onto flood
                        neighbour.flooding <- true
                    end
                end
            end
        else
            # Item is above water
            item.flooding <- false
            if item.fenced = false then
                push item onto fence
                item.fenced <- true
            end
        end

    end
end


                        
这篇关于在3d棋盘中找到水量的提示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！