Решение задачи 14.
Для реализации данного алгоритма нам понадобится структура данных "очередь". Очередь в программировании, как и очередь в магазине, имеет начало и конец. Если приходит новый элемент, то он становится в конец очереди, если необходимо взять элемент из очереди, то он берется из ее начала. Очередь будем представлять в виде массива. Пусть у нас есть индекс первого - 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);
begin
FIN:=FIN+1; {на первое свободное место}
Queue[FIN]:=x; {ставим элемент x}
end;
Procedure OutQueue (var x : element);
begin
x:=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 begin
OutQueue(Current);
for i:=1 to 4 do begin
neighbor.x:=Current.x+Delta[i,1], neighbor.y:=Current.y+Delta[i,2],
if A[neighbor.x,neighbor.y]=z
then 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 begin
A[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 begin
A[0,j]:=0; A[N+1,j]:=0;
end;
|
