c++ - 在 3d 棋盘中查找水量的提示

标签 c++ recursion volume

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

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

其中 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,

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

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

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

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

最佳答案

有趣的问题，有许多不同的解决方案。今天下午我一直在考虑这个问题，我会选择使用优先级队列(也许是最小堆)进行洪水填充之类的东西。我们称它为 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

关于c++ - 在 3d 棋盘中查找水量的提示，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15033555/

上一篇：c++ - 带有指向数据成员的指针的 std::thread

下一篇：c++ - OpenCv 将 cv::waitKey 限制为只等待一个特定的键？

相关文章：

c++ - 如何模拟 Qt 中的崩溃？

c++ - 需要在 C++ 中使用 Qt 4.7 创建 http 网络服务器

c - 递归释放C中的TRIE结构

iphone - iPhone Objective C-铃声音量和应用内音量之间的差异

python - 基于 curses UI 的 slider

c++ - 列表容器 - 使用不相关的类型存储和移除

c++ - 如何使#include-file 的内容成为 cpp 文件中的编译时常量？

function - 将递归函数转化为尾递归

haskell - 一次处理列表 1..n 个元素，无需显式递归

ios - 播放结束后将音量控制返回到 iOS 设备铃声

©2024 IT工具网  联系我们