そのため、それぞれ高さが異なる正方形の 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;
}
私が見つけているのは、上、下、左、右の正方形の高さだけです。
現在、高さが小さい場合に水が正方形にこぼれることを知って、総体積を取得する方法を見つけようとして立ち往生しています。これを見れば見るほど、再帰的に行うべきだと思いますが、それを実装する方法が見つかりません。
どんな助けでも大歓迎です。私がしなければならないことへの正しい方向へのプッシュのためだけに答えを探しているのではありません。