Databases
StackOverflow2013
Postsdbo
POTips on finding the volume of water in a 3d chess board
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POTips on finding the volume of water in a 3d chess board
    primarykey
    data
    text
    <p>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. </p> <pre><code>int CalcContainedWater( const int *p_data, int num_columns, int num_rows ) </code></pre> <p>Where <code>p_data</code> 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.</p> <p>Keep in mind the value inside of <code>p_data</code> can hold both positive and negative values for the heights.</p> <p>For example:</p> <p>A) The following board yields a containment of 3.</p> <pre><code>1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, </code></pre> <p>B) The following board yields a containment of 0.</p> <pre><code>1, 0, 1, 1, 0, 1, 1, 1, 1, </code></pre> <p>C) The following board yields a containment of 1.</p> <pre><code>0, 1, 0, 1, 0, 1, 0, 1, 0, </code></pre> <p><strong>This is what I have so far :</strong></p> <pre><code> #include "stdafx.h" #include &lt;queue&gt; #include &lt;vector&gt; 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&lt; typename FirstType, typename SecondType &gt; struct PairComparator { bool operator()( const pair&lt;FirstType, SecondType&gt;&amp; p1, const pair&lt;FirstType, SecondType&gt;&amp; p2 ) const { return p1.second &gt; 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&lt;pair&lt;int,int&gt;, vector&lt;pair&lt;int,int&gt;&gt;, PairComparator&lt;int,int&gt;&gt; qPerimeter; queue&lt;pair&lt;int,int&gt;&gt; qFlooding; vector&lt;Square&gt; vSquareVec(num_columns * num_rows); int nTotalContained = 0; int nCurrentSqHeight = 0; int nCurrWaterLvl = 0; int nDepth = 1; for( int nRow = 0; nRow &lt; num_rows; ++nRow) { for( int nColumn = 0; nColumn &lt; num_columns; ++ nColumn) { int nCurrArrayPoint = nRow * num_columns + nColumn; nCurrentSqHeight = p_data[nCurrArrayPoint]; Square sSquare(nCurrentSqHeight, nCurrArrayPoint, FREE, false,false,false); if(nRow == 0 &amp;&amp; nColumn == 0) sSquare.gPos = TOP_LEFT_CORNER; else if(nRow == 0 &amp;&amp; nColumn == num_columns - 1) sSquare.gPos = TOP_RIGHT_CORNER; else if(nRow == num_rows - 1 &amp;&amp; nColumn == 0) sSquare.gPos = BOTTOM_LEFT_CORNER; else if(nRow == num_rows - 1 &amp;&amp; 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&lt;int,int&gt; p1(nCurrArrayPoint, nCurrentSqHeight); qPerimeter.push(p1); } } } nCurrWaterLvl = qPerimeter.top().second; while( !qPerimeter.empty() ) { pair&lt;int,int&gt; PerimPos = qPerimeter.top(); qPerimeter.pop(); if( !vSquareVec[PerimPos.first].bIsVisited ) { if( vSquareVec[PerimPos.first].nHeight &gt; nCurrWaterLvl ) nCurrWaterLvl = vSquareVec[PerimPos.first].nHeight; vSquareVec[PerimPos.first].bIsFlooding = true; qFlooding.push(PerimPos); while( !qFlooding.empty() ) { pair&lt;int,int&gt; FloodPos = qFlooding.front(); qFlooding.pop(); nDepth = nCurrWaterLvl - vSquareVec[FloodPos.first].nHeight; if( nDepth &gt;= 0) { vSquareVec[FloodPos.first].bIsVisited = true; pair&lt;int,int&gt; newFloodPos; switch(vSquareVec[FloodPos.first].gPos) { case TOP_LEFT_CORNER: if( !vSquareVec[FloodPos.first + 1].bIsVisited &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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 &amp;&amp; !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; } </code></pre> <p>All I'm finding is the top,bottom, left and right square heights.</p> <p>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.</p> <p>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. </p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USErik
    1. USTCoder
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POTips on finding the volume of water in a 3d chess board
      1. USDave Rager
      1. VTFavorite
    2. VO
      singulars
      1. POTips on finding the volume of water in a 3d chess board
      1. USTCoder
      1. VTFavorite
    3. VO
      singulars
      1. POTips on finding the volume of water in a 3d chess board
      1. USDave S
      1. VTFavorite
    1. COInteresting, despite all appearances, I'd call this a path-finding problem.
      singulars
      1. POTips on finding the volume of water in a 3d chess board
      1. USMooing Duck
    2. COFrom each square, find the path from that square to an edge, where you minimize the height of the highest square you cross. Each square holds water equal to the height of the highest square it's path crossed minus it's starting height. Then sum those for an answer. Of course, that's all theory, There's far easier/faster/better designs for doing this in a practical manner.
      singulars
      1. POTips on finding the volume of water in a 3d chess board
      1. USMooing Duck
    3. COYea my whole thought process behind it is very similar to what you are talking about.
      singulars
      1. POTips on finding the volume of water in a 3d chess board
      1. USTCoder
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload