c++ - 3D チェス盤の水の体積を見つけるためのヒント

Question

そのため、それぞれ高さが異なる正方形の RxC グリッドである 3D チェス盤を再作成する必要がある課題があります。チェス盤が水密で、誰かが水を保持できなくなるまで水を全体に注ぐと、一定量の水が保持されます。ボードがすでに最大量の水を保持している場合、ボードに注がれた余分な水は端から流れ落ちます。ボードを囲む背の高い容器はありません。チェス盤の正方形は 1 インチ四方で、高さはインチで示されていると仮定できます。

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

p_dataは、符号付き整数の連続する 2 次元行優先配列の最初の要素へのポインターです。関数は、さまざまな形状と内容のボードの参照実装に対してテストされ、その正確性が判断されます。

の内部の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;
    }

私が見つけているのは、上、下、左、右の正方形の高さだけです。

現在、高さが小さい場合に水が正方形にこぼれることを知って、総体積を取得する方法を見つけようとして立ち往生しています。これを見れば見るほど、再帰的に行うべきだと思いますが、それを実装する方法が見つかりません。

どんな助けでも大歓迎です。私がしなければならないことへの正しい方向へのプッシュのためだけに答えを探しているのではありません。

Answer 1

多くのさまざまな解決策がある楽しい質問です。私は今日の午後それについて考えていて、優先キュー (おそらく最小ヒープ) を使用したフラッドフィルのようなものに行きます。と呼びましょうfence。

また、どのアイテムが訪問されたかを追跡する必要があります。最初に、すべてのアイテムを未訪問としてマークします。

グリッドの周囲のすべてのポイントを に追加することから始めますfence。

次のようにループします。

からフロントアイテムをポップしfenceます。境界の最も低いポイントの 1 つを選択しました。

• アイテムが訪問された場合、それを破棄して再度ループします。
• 訪れていない場合、その高さが現在の水位よりも高い場合にのみ、その高さが新しい水位になります。

その時点からフラッド フィルを実行します。これは再帰的に (深さ優先) 実行できますが、順序付けされていないキュー (幅優先) を使用して説明します。このキューを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

Answer 2

これには、単にボリュームを計算するだけでは不十分です。

投稿した例によると、最初に封じ込めをテストしてから、コンテナの容量について心配します。

ボードに閉じたポリゴンがあるかどうかを判断することをお勧めします。
ポリゴンが閉じている場合は、その面積を決定します。
体積計算に使用される高さは、すべての境界壁の最小の高さになります。
最後に、ボリュームは最小の高さにポリゴンの面積を掛けたものになります。

頂点または線分のベクトルに基づいて閉じたポリゴンを決定するアルゴリズムについては、Webで調べてください。

Answer 3

これは、@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