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

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

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

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

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

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

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

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

现在你像这样循环：

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

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

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

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

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

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

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

初始设置：

## Clear flags.  Note I've added a 'flooding' flagfor 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 queueend## Set up perimeterfor each item on edge of map (top,left,right,bottom)    push item onto fenceendwaterlevel <- 0total <- 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    endend

总结

以上是内存溢出为你收集整理的c – 在3d棋盘中找到水量的提示全部内容，希望文章能够帮你解决c – 在3d棋盘中找到水量的提示所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。