Для реализации данного алгоритма нам понадобится структура данных "очередь". Очередь в программировании, как и очередь в магазине, имеет начало и конец. Если приходит новый элемент, то он становится в конец очереди, если необходимо взять элемент из очереди, то он берется из ее начала. Очередь будем представлять в виде массива. Пусть у нас есть индекс первого - BEG и последнего FIN элементов очереди (если очередь пуста, то BEG=FIN+1; сначала же BEG=1, FIN=0).
Очередь опишем так: var Queue=array[1..MaxQ] of element;
Тут MaxQ - максимальное число элементов в очереди, element какой-то тип данных. В задаче ниже в качестве element можно взять такой type element = record x: byte; y: byte; end; где element - это запись, состоящая из x-овой и y-овой координаты элемента матрицы A=array[0..M+1,0..N+1] of integer. Индексы матрицы принимают такое значение из-за того, что мы будем окаймлять матрицу нулевыми элементами (так будет проще проверять выливание за край фигуры).
С очередью можно проводить операции:
вставка в очередь InQueue,
удаление из очереди OutQueue.
Procedure InQueue (x : element);beginFIN:=FIN+1; {на первое свободное место}Queue[FIN]:=x; {ставим элемент x}end;Procedure OutQueue (var x : element);beginx:=Queue[BEG]; {берем первый элемент}BEG:=BEG+1; {и изменяем указатель}{на следующий за ним}
end;
Находим максимальный элемент D в матрице A. Пока все элементы в матрице A не станут равны D, повторяем следующую последовательность действий:
а) Находим в матрице минимальный ненулевой элемент z (если их несколько, то берем любой из них), и заносим его в очередь (очередь сначала пустая). Если этот минимальный ненулевой элемент z=D, то СТОП.
Сначала считаем, что p=D - это минимальный граничный элемент области, заполненной элементами со значением z.
б) Для каждого еще не просмотренного элемента очереди (пусть в матрице этот элемент находится в позиции (i,j)) повторяем следующее:
Для каждого соседа (сверху, снизу, справа, слева) данного элемента (i,j) проводим проверку-просмотр:
ЕСЛИ (сосед <> z) ТО P=min{P,сосед} ИНАЧЕ ЕСЛИ сосед еще не просмотрен ТО координата соседа - в очередь (в очереди появился еще один непросмотренный элемент) т.е. мы ищем минимальный окаймляющий элемент области, заполненной элементами со значением z.
Фрагмент программы поиска:
var Delta = array [1..4,1..2] of integer = ((0,1),(1,0),(-1,0),(0,-1));{Delta - возможные смещения соседних клеток от текущей клетки}Current, neighbor : element;z : integer;....{Будем обозначать то, что элемент в матрице уже просмотрен}{умножением его на -1}{минимальный ненулевой элемент матрицы имеет значение z}while BEG<>FIN+1 do beginOutQueue(Current);for i:=1 to 4 do beginneighbor.x:=Current.x+Delta[i,1], neighbor.y:=Current.y+Delta[i,2],if A[neighbor.x,neighbor.y]=zthen InQueue(neighbor)else p:=min(A[neighbor.x,neighbor.y],p); end;
end;
Если в очереди нет больше непросмотренных элементов, то, если p<z (случай, когда данная область имеет "слив" за границы матрицы) в матрице во все просмотренные элементы из очереди заносим значение D (делаем их равными накопленному значению, чтобы больше их не рассматривать).
Если же p>z, то высчитываем, сколько воды поместится в "бассейн" с глубиной дна z и с высотой ограждающего бордюра p:
Объем = (p-z)* количество просмотренных элементов в очереди.
Добавляем полученный объем к ранее найденному объему воды,заполняющему матрицу до высоты x. Заполняем в матрице элементы, соответствующие просмотренным элементам из очереди, значением p ("Доливаем" воды в "бассейн" до уровня p). Переход на пункт а).
Суммарный полученный объем воды и является искомым.
Окаймление матрицы, упомянутое выше, может выглядеть следующим образом: матрица [1..N, 1..M] окаймляется нулями так: вводятся дополнительные нулевые 0-ая и (N+1)-ая строки и 0-ой и (M+1)-ый столбцы
var A: array[0..N+1,0..M+1] of byte;{ввод и окаймление нулями}for i:=1 to N do beginA[i,0]:=0; A[i,M+1]:=0;for j:=1 to M do read(A[i,j]);end;for j:=0 to M+1 do beginA[0,j]:=0; A[N+1,j]:=0;end;
