5

所以我有一个任务，我必须重新创建一个 3d 棋盘，它是一个 RxC 方格，每个方格都有不同的高度。如果棋盘是不透水的，有人把水倒在上面，直到它不能再盛水，它就会盛住一定量的水。如果板子已经装满了最大量的水，任何倒在板上的多余水都会从边缘排出，板子周围没有高大的容器。你可以假设棋盘上的方格是一平方英寸，高度以英寸为单位。

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

wherep_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,

C) 下面的棋盘产生 1 的遏制。

0, 1, 0,
1, 0, 1,
0, 1, 0,

这是我到目前为止所拥有的：

    #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;
    }

我所找到的只是顶部、底部、左侧和右侧的正方形高度。

目前，我一直在试图弄清楚如何获得总体积，因为如果它们的高度较小，水会溢出到正方形上。我看的越多，我就越认为它应该递归地完成，但找不到实现它的方法。

任何帮助将非常感激。不只是为了朝着正确的方向推进我需要做的事情而寻找答案。

4

5 回答 5

3

有趣的问题，有许多不同的解决方案。今天下午我一直在考虑这个问题，我会使用优先队列（也许是最小堆）进行洪水填充。我们称它为fence.

您还需要跟踪访问过的项目。最初将所有项目标记为未访问。

首先将网格周边的所有点添加到fence.

现在你像这样循环：

从 中弹出前面的项目fence。您已选择周长上的最低点之一。

  • 如果该项目已被访问，则丢弃它并再次循环。
  • 如果它未被访问，则只有当它大于当前水位时，它的高度才会成为您的新水位。

您现在从该点开始进行洪水填充。您可以递归地执行此操作（深度优先），但我将使用无序队列（广度优先）进行讨论。我们称这个队列为flood. 您首先将项目推到flood.

洪水然后是这样的：循环直到没有剩余的项目flood......

  • 弹出一个项目flood
  • 如果它已经被访问过，忽略它并再次循环。
  • 如果项目高度小于或等于当前水位，请计算高度差并将其添加到您的总体积中。将项目标记为已访问，然后将所有未访问的邻居添加到flood。
  • 如果项目高度大于当前水位，只需将其添加到fence. 您将需要一种方法来判断该项目是否已经存在fence- 您不想再次添加它。也许您可以扩展您的“已访问”标志以应对此问题。

就是这样。诚然，这只是一个思想实验，当我躺在那里感到宿醉和肮脏时，但我认为这很好。

正如你所要求的......一些伪代码。

最初设定：

## 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

现在是算法的主要部分

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
于 2013-02-23T03:28:12.153 回答
0

这不仅仅是简单地计算体积。

根据您发布的示例，您首先要测试容器，然后再担心容器的体积。

我建议确定板上是否存在封闭多边形。
如果多边形是闭合的，确定它的面积。
用于体积计算的高度将是所有围墙的最小高度。
最后，体积将是最小高度乘以多边形的面积。

基于顶点或线段向量确定闭合多边形的网络算法研究。

于 2013-02-22T21:42:12.123 回答
0

这有点蛮力，但可能会奏效。

您可能会尝试在概念上将电路板分成几层，例如：

-------------------------
0 | 1 | 1 | 0 | 1 | 1 | 0
1 | 0 |-1 | 1 | 0 | 0 | 1
1 | 1 | 1 | 1 | 1 | 1 | 1
-------------------------

只看最低层。假设 -1 是底部，板将如下所示：

-------------------------
0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 |-1 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0
-------------------------

对于每个正方形，确定左侧、右侧、顶部和底部是否存在一个均具有更大值的正方形。在这种情况下，我们数 1。

然后移动到下一层，填补最后一层的“洞”。

-------------------------
0 | 1 | 1 | 0 | 1 | 1 | 0
1 | 0 | 0 | 1 | 0 | 0 | 1
1 | 1 | 1 | 1 | 1 | 1 | 1
-------------------------

冲洗，重复。在这一层中，我们数 4，总共为 5。

-------------------------
1 | 1 | 1 | 1 | 1 | 1 | 1
1 | 1 | 1 | 1 | 1 | 1 | 1
1 | 1 | 1 | 1 | 1 | 1 | 1
-------------------------

顶层显然没有，我们完成了。

在伪代码中：

for each layer l in layers
   for each square in l
      if there exists a square left, right, top and bottom with higher value
          count the square.

编辑

当然，既然我有严重的问题，今天早上我醒来的第一件事就是想到这个问题，并立即打破了我的解决方案。

让我们对示例进行一项更改：

-------------------------
0 | 1 | 1 | 0 | 1 | 1 | 0
1 | 0 |-1 | 1 | 0 | 0 | 1
1 | 1 | 1 | 1 | 1 | 0 | 1
-------------------------
                    ^

在外面开一个洞。使用当前算法，我们将得到 4 的解，这显然是错误的。

为了解决这个问题，我们需要实现一个回溯算法。

我们不是在左边、右边、顶部和底部的任何地方寻找更高的值，而是只检查紧邻的方块。如果有任何高度相同，我们也需要访问该广场并再次执行检查。如果我们找到通往外面的路，那么原始方块（以及随后所有访问过的方块）都会失败。如果我们遇到了死胡同，那么所有访问过的方格都可以计算在内。

通过这种修改，我们将得到正确的结果 3。

于 2013-02-22T22:39:32.557 回答
0

这是一段工作代码：基本思想是将棋盘水平分割成多个级别，并确定每个级别可以容纳的体积（复杂度 O(x * y * z)）：

#include <stdio.h>
#include <memory.h>

// The Cell structure for each level
struct Cell
{
    unsigned char height; // either 0 or 1
    bool visited; // we only visit the cells that have height of 0
};

// The recursive function that visits a cell, accumulate the water volume (or if leaked due to being at the border, reset the values); it also
// looks to its 4 adjacent cells (if valid) recursively.
// Note that the top level function actually attempts to visit *all* the "connected" cells (and mark them as visited, so they will not be visited again)
// From the top level, the cells are thus visited in "chunks" (as long as they are connected)
void VisitCell(Cell* one_level_cells, unsigned short a_w, unsigned short a_h, unsigned short w, unsigned short h, unsigned __int64* sum, bool* leaked)
{
    Cell& cell = one_level_cells[h * a_w + w];
    if (cell.height == 0 && !cell.visited)
    {
        cell.visited = true;
        if (w == 0 || w + 1 == a_w || h == 0 || h + 1 == a_h)
        {
            // I am at the border while I am not guarding the water, the water for this "chunk" is then leaked!
            *leaked = true;
            *sum = 0;
        }

        if (!*leaked)
        {
            // potentially increment the volume, until it's detected leaked at some point
            ++*sum;
        }

        if (w < a_w - 1)    VisitCell(one_level_cells, a_w, a_h, w+1, h, sum, leaked);
        if (w > 0)          VisitCell(one_level_cells, a_w, a_h, w-1, h, sum, leaked);
        if (h < a_h - 1)    VisitCell(one_level_cells, a_w, a_h, w, h+1, sum, leaked);
        if (h > 0)          VisitCell(one_level_cells, a_w, a_h, w, h-1, sum, leaked);
    }
}

//@param int const * const unsigned short *a_board - argument representing the NxM board.
//@param unsigned short a_w - argument representing the width of the board
//@param unsigned short a_h - argument representing the height of the board
//@return - unsigned __int64 - the volume of water the board retains

// complexity: O(a_w * a_h * max_height)
unsigned __int64 CalculateVolume(const unsigned short *a_board, unsigned short a_w, unsigned short a_h)
{
    if (!a_board || a_w < 3 || a_h < 3)
    {
        return 0;
    }
    // Basic algorithm: slice the board horizontally into as many levels as the maximum height of the board
    // for each sliced level, determine the water volume cubed so far, and the total volume is the sum of the volume of the individual level
    unsigned __int32 n = a_w * a_h;
    unsigned short max_height = 0;
    for (unsigned __int32 i = 0; i < n; ++i)
    {
        if (max_height < a_board[i])
        {
            max_height = a_board[i];
        }
    }
    unsigned short *board = new unsigned short[n];
    memcpy(board, a_board, n * sizeof(unsigned short));
    Cell* one_level_cells = new Cell[n];
    unsigned __int64 total_volume = 0;
    for (unsigned short i = 0; i < max_height; ++i)
    {
        // form a new current level of cells (and update the copy of the board accordingly)
        unsigned __int64 volume_this_level = 0;
        for (unsigned __int32 j = 0; j < n; ++j)
        {
            if (board[j] > 0)
            {
                --board[j];
                one_level_cells[j].height = 1;
            }
            else
            {
                one_level_cells[j].height = 0;
            }
            one_level_cells[j].visited = false;
        }

        // visit all the cells within the current level
        // we mark the cells after being visited, and the cells are visited in "chunks" when they are "connected" together
        // so effectively, most of the top level cell visiting would return immediately, rather than trying to revisit the cells again and again
        for (unsigned short h = 0; h < a_h; ++h)
        {
            for (unsigned short w = 0; w < a_w; ++w)
            {
                unsigned __int64 sum = 0;
                bool leaked = false;
                // NB: the top level function here will attempt to cover *all* the connected cells at the current level (in the recursion)
                // so even though we are still iterating through all the cells at the top level, most of them should find that the cell has been visited
                // so the sum here is actually a "chunked" sum in the perception of the top level cells
                VisitCell(one_level_cells, a_w, a_h, w, h, &sum, &leaked);
                volume_this_level += sum;
            }
        }

        total_volume += volume_this_level;
    }

    delete[] one_level_cells;
    delete[] board;

    return total_volume;
}

int main()
{
    // feel free to play with this board
    unsigned short board[] = {
        2, 2, 2, 2, 2, 2, 2, 2,
        2, 1, 1, 1, 1, 1, 1, 2,
        2, 1, 2, 3, 3, 2, 1, 2,
        2, 1, 3, 1, 1, 3, 1, 2,
        2, 1, 3, 1, 1, 3, 1, 2,
        2, 1, 2, 3, 3, 2, 1, 2,
        2, 1, 1, 1, 1, 1, 1, 2,
        2, 2, 2, 2, 2, 2, 2, 2,
    };
    printf("Volume: %lld\n", CalculateVolume(board, 8, 8));
    return 0;
}
于 2014-07-14T20:20:47.110 回答
0

这是@paddy 的python(2.7) 版本的伪代码。希望这会对某人有所帮助。

import heapq
block =[
1, 2, 3,
4 ,2,6,
7, 0,5,
11,15, 13,
14,15,16,
1,0,1,
1,1,1]
cmax =3; 
rmax =7;
items =[]
fence = []
flood = []
waterlevel = 0
total = 0
class Item(object):
    visited = False
    fenced = False
    flooding = False
    height= 0
    index = 0
i=0
## initializing blocks
for val in block:    
    item =  Item();
    item.height = val
    item.index = i
    i+=1
    items.append((item.height,item))
## find out the edges  
for i in range (cmax):
    heapq.heappush(fence, items[i])
    heapq.heappush(fence, items[i+(rmax-1)*cmax])
    print items[i][1].height,items[i+(rmax-1)*cmax][1].height

for i in range(1,rmax-1):
    heapq.heappush(fence, items[cmax*i])
    heapq.heappush(fence, items[cmax*i+(cmax-1)])
    print items[cmax*i][1].height,items[cmax*i+(cmax-1)][1].height

## get neighbour
def get_neighbour(i):
    c= i%cmax
    r= i//cmax
    neighbour = []
    if (c != 0):
        neighbour.append(items[r*cmax+c-1])
    if (c != (cmax -1)):
        neighbour.append(items[r*cmax+c+1])
    if (r != 0):
        neighbour.append(items[(r-1)*cmax+c])
    if (r != (rmax -1)):    
        neighbour.append(items[(r+1)*cmax+c])
    return neighbour



while (len(fence)>0):
    item = heapq.heappop(fence)
    if(item[1].visited):
        continue
    if (item[1].height > waterlevel):
        waterlevel = item[1].height
    heapq.heappush(flood,item)
    item[1].flooding = True
    while(len(flood)>0):
        fitem = heapq.heappop(flood)
        depth = waterlevel - fitem[1].height
        if (depth >= 0):
            total += depth
            fitem[1].visited = True
            neighbour = get_neighbour(fitem[1].index)
            for nitem in neighbour:
                if nitem[1].visited == False :
                    if nitem[1].flooding == False :
                        heapq.heappush(flood,nitem)
                        nitem[1].flooding = True
        else:
            fitem[1].flooding = False
            if fitem[1].fenced == False:
                heapq.heappush(fence,fitem)
                fitem[1].fenced = True
print total
于 2016-11-18T07:24:15.680 回答