c – 在3d棋盘中找到水量的提示

发布时间：2020-12-16 05:03:26 所属栏目：百科来源：网络整理

导读：所以我有一个任务,我必须重新创建一个3D棋盘,这是一个RxC网格的正方形,每个正方形都是不同的高度.如果棋盘是水密的,并且有人在它上面浇水直到它不能再容纳水,它将保持固定量的水.如果电路板已经保持其最大水量,则任何多余的水倒在电路板上都会从边缘排出,电

所以我有一个任务,我必须重新创建一个3D棋盘,这是一个RxC网格的正方形,每个正方形都是不同的高度.如果棋盘是水密的,并且有人在它上面浇水直到它不能再容纳水,它将保持固定量的水.如果电路板已经保持其最大水量,则任何多余的水倒在电路板上都会从边缘排出,电路板周围没有高大的容器.你可以假设棋盘上的方格是一平方英寸,高度是以英寸为单位.

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

其中p_data是指向连续的二维,有符号整数的行主要数组的第一个元素的指针.您的功能将针对不同形状和内容的电路板的参考实现进行测试,以确定其正确性.

请记住,p_data中的值可以包含高度的正值和负值.

例如：

A)以下板块产生3的遏制.

1,1,

B)以下板产生0的遏制.

1,

C)以下板产生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_rows );

int CalcContainedWater( const int *p_data,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,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;
    }

我所发现的只是顶部,底部,左侧和右侧的高度.

目前,我一直试图弄清楚如何获得总体积,知道如果它们的高度较小,水会溢出到正方形.我越看越多,我认为它应该以递归方式完成,但无法找到实现它的方法.

任何帮助将非常感激.没有找到答案只是为了向正确的方向推进我需要做的事情.

解决方法

有趣的问题,有许多不同的解决方案我今天下午一直在考虑它,我会选择像洪水一样的优先级队列(也许是最小堆).我们称之为围栏.

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

首先将栅格周围的所有点添加到栅栏中.

现在你像这样循环：

从围栏中弹出前面的项目.您已选择周长中的最低点之一.

>如果已访问该项目,请将其丢弃并再次循环.
>如果未经检查,只有当水位高于当前水位时,其高度才会成为新的水位.

你现在从那一点做洪水填充.你可以递归地执行此操作(深度优先),但我将使用无序队列(广度优先)来讨论这个问题.让我们称这个队列为洪水.首先将项目推入洪水.

洪水然后是这样的：循环,直到洪水中没有剩余物品……

>从洪水中弹出一个项目
>如果已经访问过,请忽略它并再次循环.
>如果物品高度小于或等于当前水位,请计算高度差并将其添加到总体积中.将项目标记为已访问,然后将所有未访问的邻居添加到洪水中.
>如果物品高度大于当前水位,只需将其添加到围栏.你想要有一种方法来判断该物品是否已经在栅栏中 – 你不想再添加它.也许你可以扩展你的“访问”标志来应对这一点.

就是这样.不可否认,这只是一个思想实验,当我躺在感觉宿醉和肮脏,但我认为这是好的.

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

初始设置：

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!