Menu
So I have an assignment where I have to recreate a 3d chessboard that is a RxC grid of squares each being a different height. If the chessboard is water tight, and someone pours water all over it until it can hold no more water, it will hold a fixed amount of water. If the board is already holding its maximum volume of water, any excess water poured onto the board will drain off the edges, there is no tall container surrounding the board. You can assume the squares on the chess board are one inch square, and the heights are given in inches.
int CalcContainedWater( const int *p_data, int num_columns, int num_rows )
Where p_data is a pointer to the first element of a contiguous two-dimensional, row-major array of signed integers. Your function will be tested against a reference implementation for boards of varying shapes and contents to determine its correctness.
Keep in mind the value inside of p_data can hold both positive and negative values for the heights.
For example:
A) The following board yields a containment of 3.
1, 1, 1, 1, 1,
1, 0, 0, 0, 1,
1, 1, 1, 1, 1,
B) The following board yields a containment of 0.
1, 0, 1,
1, 0, 1,
1, 1, 1,
C) The following board yields a containment of 1.
0, 1, 0,
1, 0, 1,
0, 1, 0,
This is what I have so far :
#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;
}
All I'm finding is the top,bottom, left and right square heights.
Currently I'm stuck trying to figure out out how to get the total volume knowing that water will spill over to squares if they are smaller in height. The more that I look at this the more I think that it should be done recursively but can't find a way to implement it.
Any help would be much appreciated. Not looking for the answer just for a push into the right direction into what I need to do.
941
Fun question, with many varied solutions. I've been thinking about it this afternoon and I would go for something like flood-fill with a priority queue (min-heap, perhaps). Let's call it the fence.
You'll also want to keep track of which items have been visited. Mark all items as unvisited, initially.
Start off by adding all points around the perimeter of your grid to the fence.
Now you loop like so:
Pop the front item from the fence. You have selected one of the lowest points on the perimeter.
You now do a flood-fill from that point. You can do this recursively (depth-first), but I will discuss this using an unordered queue (breadth-first). Let's call this queue the flood. You start by pushing the item onto flood.
Flooding then goes like this: Loop until there are no items remaining in flood...
flood
flood.fence. You'll want to have a way to tell whether the item is already in fence - you don't want to add it again. Maybe you can extend your 'visited' flags to cope with this.And that's it. Admittedly it was just a thought experiment while I lay around feeling hungover and seedy, but I reckon it's good.
As you requested... Some pseudocode.
Initial setup:
## 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
Now the main chunk of the algorithm
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
