Советы по поиску объема воды в 3D шахматной доске

Question

Советы по поиску объема воды в 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;
}

Все, что я нахожу, это верхняя, нижняя, левая и правая квадратные высоты.

В настоящее время я застрял, пытаясь выяснить, как получить общий объем, зная, что вода будет перетекать в квадраты, если они меньше по высоте. Чем больше я смотрю на это, тем больше я думаю, что это должно быть сделано рекурсивно, но не могу найти способ реализовать это.

Любая помощь приветствуется. Не ищу ответа только для того, чтобы подтолкнуть в правильном направлении то, что мне нужно сделать.

5

c++recursion volume

Решение

Другие решения

Это займет больше, чем просто расчет объема.

Согласно приведенным вами примерам, у вас есть тест на политика сдерживания Сначала беспокойтесь об объеме контейнера.

Я предлагаю определить, есть ли на доске замкнутый многоугольник.
Если полигон замкнут, определите его площадь.
Высота, используемая для расчета объема, будет минимальной высотой всех ограничивающих стен.
Наконец, объем будет минимальной высотой, умноженной на площадь многоугольника.

Исследование в сети алгоритмов определения замкнутого многоугольника на основе вектора вершин или отрезков.

0

Это немного грубая сила, но, вероятно, сработает.

Вы можете попытаться концептуально разбить доску на слои, например:

-------------------------
0 | 1 | 1 | 0 | 1 | 1 | 0
1 | 0 |-1 | 1 | 0 | 0 | 1
1 | 1 | 1 | 1 | 1 | 1 | 1
-------------------------

Глядя только на самый нижний слой. Предполагая, что -1 — это дно, доска будет выглядеть так:

-------------------------
0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 |-1 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0
-------------------------

Для каждого квадрата определите, существует ли квадрат слева, справа, сверху и снизу, который имеет большее значение. В этом случае мы считаем 1.

Затем переходите к следующему слою, заполняя «дыры» в последнем слое.

-------------------------
0 | 1 | 1 | 0 | 1 | 1 | 0
1 | 0 | 0 | 1 | 0 | 0 | 1
1 | 1 | 1 | 1 | 1 | 1 | 1
-------------------------

Промыть, повторить. В этом слое мы считаем 4, что дает нам 5.

-------------------------
1 | 1 | 1 | 1 | 1 | 1 | 1
1 | 1 | 1 | 1 | 1 | 1 | 1
1 | 1 | 1 | 1 | 1 | 1 | 1
-------------------------

Верхний слой, очевидно, не имеет ни одного, и мы закончили.

В псевдокоде:

for each layer l in layers
for each square in l
if there exists a square left, right, top and bottom with higher value
count the square.

редактировать

Конечно, поскольку со мной что-то серьезно не так, когда я проснулся этим утром, первое, о чем я подумал, была эта проблема, и я сразу же сломал свое решение.

Давайте сделаем одно изменение в примере:

-------------------------
0 | 1 | 1 | 0 | 1 | 1 | 0
1 | 0 |-1 | 1 | 0 | 0 | 1
1 | 1 | 1 | 1 | 1 | 0 | 1
-------------------------
^

Откройте отверстие снаружи. С текущим алгоритмом мы получили бы решение 4, которое, очевидно, неправильно.

Чтобы это исправить, нам нужно реализовать алгоритм обратного слежения.

Вместо того, чтобы смотреть куда-либо влево, вправо, сверху и снизу для более высокого значения, мы проверяем только непосредственно смежные квадраты. Если они находятся на той же высоте, мы должны посетить этот квадрат и снова выполнить проверку. Если мы найдем дорогу наружу, то исходный квадрат (а впоследствии и все посещенные квадраты) потерпят неудачу. Если мы зашли в тупик, то все посещенные квадраты могут быть подсчитаны.

С этой модификацией мы получили бы правильный результат 3.

0

Вот фрагмент рабочего кода: основная идея — разделить доску по горизонтали на уровни и определить объем, который может вместить каждый уровень (сложность O (x * y * z)):

#include <stdio.h>
#include <memory.h>

// The Cell structure for each level
struct Cell
{
unsigned char height; // either 0 or 1
bool visited; // we only visit the cells that have height of 0
};

// The recursive function that visits a cell, accumulate the water volume (or if leaked due to being at the border, reset the values); it also
// looks to its 4 adjacent cells (if valid) recursively.
// Note that the top level function actually attempts to visit *all* the "connected" cells (and mark them as visited, so they will not be visited again)
// From the top level, the cells are thus visited in "chunks" (as long as they are connected)
void VisitCell(Cell* one_level_cells, unsigned short a_w, unsigned short a_h, unsigned short w, unsigned short h, unsigned __int64* sum, bool* leaked)
{
Cell& cell = one_level_cells[h * a_w + w];
if (cell.height == 0 && !cell.visited)
{
cell.visited = true;
if (w == 0 || w + 1 == a_w || h == 0 || h + 1 == a_h)
{
// I am at the border while I am not guarding the water, the water for this "chunk" is then leaked!
*leaked = true;
*sum = 0;
}

if (!*leaked)
{
// potentially increment the volume, until it's detected leaked at some point
++*sum;
}

if (w < a_w - 1)    VisitCell(one_level_cells, a_w, a_h, w+1, h, sum, leaked);
if (w > 0)          VisitCell(one_level_cells, a_w, a_h, w-1, h, sum, leaked);
if (h < a_h - 1)    VisitCell(one_level_cells, a_w, a_h, w, h+1, sum, leaked);
if (h > 0)          VisitCell(one_level_cells, a_w, a_h, w, h-1, sum, leaked);
}
}

//@param int const * const unsigned short *a_board - argument representing the NxM board.
//@param unsigned short a_w - argument representing the width of the board
//@param unsigned short a_h - argument representing the height of the board
//@return - unsigned __int64 - the volume of water the board retains

// complexity: O(a_w * a_h * max_height)
unsigned __int64 CalculateVolume(const unsigned short *a_board, unsigned short a_w, unsigned short a_h)
{
if (!a_board || a_w < 3 || a_h < 3)
{
return 0;
}
// Basic algorithm: slice the board horizontally into as many levels as the maximum height of the board
// for each sliced level, determine the water volume cubed so far, and the total volume is the sum of the volume of the individual level
unsigned __int32 n = a_w * a_h;
unsigned short max_height = 0;
for (unsigned __int32 i = 0; i < n; ++i)
{
if (max_height < a_board[i])
{
max_height = a_board[i];
}
}
unsigned short *board = new unsigned short[n];
memcpy(board, a_board, n * sizeof(unsigned short));
Cell* one_level_cells = new Cell[n];
unsigned __int64 total_volume = 0;
for (unsigned short i = 0; i < max_height; ++i)
{
// form a new current level of cells (and update the copy of the board accordingly)
unsigned __int64 volume_this_level = 0;
for (unsigned __int32 j = 0; j < n; ++j)
{
if (board[j] > 0)
{
--board[j];
one_level_cells[j].height = 1;
}
else
{
one_level_cells[j].height = 0;
}
one_level_cells[j].visited = false;
}

// visit all the cells within the current level
// we mark the cells after being visited, and the cells are visited in "chunks" when they are "connected" together
// so effectively, most of the top level cell visiting would return immediately, rather than trying to revisit the cells again and again
for (unsigned short h = 0; h < a_h; ++h)
{
for (unsigned short w = 0; w < a_w; ++w)
{
unsigned __int64 sum = 0;
bool leaked = false;
// NB: the top level function here will attempt to cover *all* the connected cells at the current level (in the recursion)
// so even though we are still iterating through all the cells at the top level, most of them should find that the cell has been visited
// so the sum here is actually a "chunked" sum in the perception of the top level cells
VisitCell(one_level_cells, a_w, a_h, w, h, &sum, &leaked);
volume_this_level += sum;
}
}

total_volume += volume_this_level;
}

delete[] one_level_cells;
delete[] board;

return total_volume;
}

int main()
{
// feel free to play with this board
unsigned short board[] = {
2, 2, 2, 2, 2, 2, 2, 2,
2, 1, 1, 1, 1, 1, 1, 2,
2, 1, 2, 3, 3, 2, 1, 2,
2, 1, 3, 1, 1, 3, 1, 2,
2, 1, 3, 1, 1, 3, 1, 2,
2, 1, 2, 3, 3, 2, 1, 2,
2, 1, 1, 1, 1, 1, 1, 2,
2, 2, 2, 2, 2, 2, 2, 2,
};
printf("Volume: %lld\n", CalculateVolume(board, 8, 8));
return 0;
}

0

Это python (2.7) версия псевдокода от @paddy. Надеюсь, это кому-нибудь поможет.

import heapq
block =[
1, 2, 3,
4 ,2,6,
7, 0,5,
11,15, 13,
14,15,16,
1,0,1,
1,1,1]
cmax =3;
rmax =7;
items =[]
fence = []
flood = []
waterlevel = 0
total = 0
class Item(object):
visited = False
fenced = False
flooding = False
height= 0
index = 0
i=0
## initializing blocks
for val in block:
item =  Item();
item.height = val
item.index = i
i+=1
items.append((item.height,item))
## find out the edges
for i in range (cmax):
heapq.heappush(fence, items[i])
heapq.heappush(fence, items[i+(rmax-1)*cmax])
print items[i][1].height,items[i+(rmax-1)*cmax][1].height

for i in range(1,rmax-1):
heapq.heappush(fence, items[cmax*i])
heapq.heappush(fence, items[cmax*i+(cmax-1)])
print items[cmax*i][1].height,items[cmax*i+(cmax-1)][1].height

## get neighbour
def get_neighbour(i):
c= i%cmax
r= i//cmax
neighbour = []
if (c != 0):
neighbour.append(items[r*cmax+c-1])
if (c != (cmax -1)):
neighbour.append(items[r*cmax+c+1])
if (r != 0):
neighbour.append(items[(r-1)*cmax+c])
if (r != (rmax -1)):
neighbour.append(items[(r+1)*cmax+c])
return neighbourwhile (len(fence)>0):
item = heapq.heappop(fence)
if(item[1].visited):
continue
if (item[1].height > waterlevel):
waterlevel = item[1].height
heapq.heappush(flood,item)
item[1].flooding = True
while(len(flood)>0):
fitem = heapq.heappop(flood)
depth = waterlevel - fitem[1].height
if (depth >= 0):
total += depth
fitem[1].visited = True
neighbour = get_neighbour(fitem[1].index)
for nitem in neighbour:
if nitem[1].visited == False :
if nitem[1].flooding == False :
heapq.heappush(flood,nitem)
nitem[1].flooding = True
else:
fitem[1].flooding = False
if fitem[1].fenced == False:
heapq.heappush(fence,fitem)
fitem[1].fenced = True
print total

0

Источник

Accepted Answer

Забавный вопрос, со многими различными решениями. Я думал об этом сегодня днем, и я хотел бы сделать что-то вроде залива с приоритетной очередью (возможно, min-heap). Давайте назовем это fence,

Вы также хотите отслеживать, какие предметы были посещены. Первоначально пометить все элементы как не посещенные.

Начните с добавления всех точек по периметру вашей сетки к fence,

Теперь вы зациклились так:

Выскочить передний элемент из fence, Вы выбрали одну из самых низких точек по периметру.

Если элемент был посещен, откажитесь от него и повторите цикл.
Если он не посещен, его высота становится вашим новым уровнем воды, только если он превышает текущий уровень воды.

Теперь вы выполняете заливку с этой точки. Вы можете сделать это рекурсивно (сначала в глубину), но я буду обсуждать это, используя неупорядоченную очередь (в ширину). Давайте назовем эту очередь flood, Вы начинаете, толкая предмет на flood,

Затем затопление происходит следующим образом: цикл пока не останется никаких элементов в flood…

Выскочить предмет из flood
Если он уже посещен, проигнорируйте его и повторите цикл.
Если высота предмета меньше или равна текущему уровню воды, вычислите разницу в высоте и добавьте ее к общему объему. Отметьте элемент как посещенный, затем добавьте всех не посещенных соседей в flood,
Если высота элемента больше текущего уровня воды, просто добавьте его в fence, Вы хотите, чтобы был способ узнать, находится ли элемент в fence — Вы не хотите добавлять это снова. Может быть, вы можете расширить свои «посещенные» флаги, чтобы справиться с этим.

И это все. По общему признанию это был только мысленный эксперимент, в то время как я лежал, чувствуя себя похмельным и убогим, но я считаю, что это хорошо.

Как вы просили … какой-то псевдокод.

Начальная настройка:

## 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

Теперь основной кусок алгоритма

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

3