Советы по поиску объема воды в 3D шахматной доске
Итак, у меня есть задание, где я должен воссоздать 3d шахматную доску, представляющую собой сетку квадратов RxC, каждый из которых имеет разную высоту. Если шахматная доска водонепроницаема, и кто-то наливает воду на нее до тех пор, пока на ней не останется больше воды, она будет удерживать фиксированное количество воды. Если на доске уже содержится максимальный объем воды, излишки воды, налитые на доску, будут стекать с краев, вокруг доски нет высокого контейнера. Можно предположить, что квадраты на шахматной доске равны одному дюйму, а высота дана в дюймах.
int CalcContainedWater( const int *p_data, int num_columns, int num_rows )
гдеp_data является указателем на первый элемент непрерывного двумерного массива строк-старших чисел со знаком. Ваша функция будет проверена на соответствие эталонной реализации для плат различной формы и содержания, чтобы определить ее правильность.
Имейте в виду значение внутриp_data может содержать как положительные, так и отрицательные значения для высот.
Например:
А) Следующая доска содержит 3.
1, 1, 1, 1, 1,
1, 0, 0, 0, 1,
1, 1, 1, 1, 1,
Б) Следующая доска содержит 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;
}
Все, что я нахожу, это верхняя, нижняя, левая и правая квадратные высоты.
В настоящее время я застрял, пытаясь выяснить, как получить общий объем, зная, что вода будет перетекать в квадраты, если они меньше по высоте. Чем больше я смотрю на это, тем больше я думаю, что это должно быть сделано рекурсивно, но не могу найти способ реализовать это.
Любая помощь приветствуется. Не ищу ответа только для того, чтобы подтолкнуть в правильном направлении то, что мне нужно сделать.