Tipps zum Ermitteln des Wasservolumens in einem 3D-Schachbrett
Ich habe also eine Aufgabe, bei der ich ein 3D-Schachbrett nachbauen muss, das ein RxC-Gitter aus Quadraten mit jeweils unterschiedlicher Höhe ist. Wenn das Schachbrett wasserdicht ist und jemand Wasser darüber gießt, bis es kein Wasser mehr aufnehmen kann, hält es eine feste Menge Wasser. Wenn die Platine bereits ihr maximales Wasservolumen enthält, läuft überschüssiges Wasser von den Rändern ab. Es gibt keinen hohen Behälter, der die Platine umgibt. Sie können davon ausgehen, dass die Quadrate auf dem Schachbrett 1 Zoll groß und die Höhen in Zoll angegeben sind.
int CalcContainedWater( const int *p_data, int num_columns, int num_rows )
Woherp_data ist ein Zeiger auf das erste Element eines zusammenhängenden zweidimensionalen, zeilengroßen Arrays von Ganzzahlen mit Vorzeichen. Ihre Funktion wird anhand einer Referenzimplementierung für Karten mit unterschiedlichen Formen und Inhalten getestet, um die Richtigkeit zu bestimmen.
Beachten Sie den Wert innerhalb vonp_data kann sowohl positive als auch negative Werte für die Höhen enthalten.
Zum Beispiel:
A) Die folgende Tafel ergibt einen Containment von 3.
1, 1, 1, 1, 1,
1, 0, 0, 0, 1,
1, 1, 1, 1, 1,
B) Die folgende Tafel ergibt einen Containment von 0.
1, 0, 1,
1, 0, 1,
1, 1, 1,
C) Die folgende Tafel ergibt einen Containment von 1.
0, 1, 0,
1, 0, 1,
0, 1, 0,
Das habe ich bisher:
#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;
}
Ich finde nur die oberen, unteren, linken und rechten quadratischen Höhen.
Momentan stecke ich fest und versuche herauszufinden, wie ich das Gesamtvolumen ermitteln kann, da ich weiß, dass Wasser in Quadrate überläuft, wenn sie eine geringere Höhe haben. Je mehr ich mir das anschaue, desto mehr denke ich, dass es rekursiv gemacht werden sollte, aber keinen Weg finden kann, es zu implementieren.
Jede Hilfe wäre sehr dankbar. Ich suche nicht nach der Antwort, nur um in die richtige Richtung zu schieben, was ich tun muss.