Найти объём скопившейся после дождя воды на тропическом острове

Текст задачи:
Предположим, в один прекрасный день вы оказались на острове прямоугольный формы.
Ландшафт этого острова можно описать с помощью целочисленной матрицы размером MxN, каждый элемент которой задаёт высоту соответствующей области острова над уровнем моря.
К примеру, вот небольшой остров размером 3x3:
4 5 4 3 1 5 5 4 1
В сезон дождей остров полностью заливает водой и в низинах скапливается вода. Низиной будем считать такую область острова, клетки которой граничат с клетками, большими по высоте. При этом диагональные соседи не учитываются, а уровень моря принимается за 0. В приведённом выше примере на острове есть только одна низина — это клетка со значением 1 в середине острова (она граничит с клетками высотой 3, 5, 5 и 4).
Таким образом, после дождя высота клеток острова изменится и станет следующей:
4 5 4 3 3 5 5 4 1
Мы видим что в данном примере высота низины изменилась с 1 до 3, после чего вода начала переливаться на соседние клетки, а затем — в море. Общий объём воды, скопившейся на острове — 2 кубические клетки.
Вот пример посложнее:
5 3 4 5 6 2 1 4 3 1 1 4 8 5 4 3
После дождя карта острова принимает следующую форму:
5 3 4 5 6 3 3 4 3 3 3 4 8 5 4 3
Общий объём скопившейся после дождя воды на таком острове составляет целых 7 кубических клеток!
Ваша программа должна быть по одному из шаблонов ниже.
На вход функции подается массив массивов, на выходе ожиается int - значения общего объёма воды, скапливающейся на острове после сезона дождей для каждого из входных примеров Ограничения: Размер острова N и M — целые числа в диапазоне [1, 50] Высоты на острове могут принимать значения из диапазона [1, 1000]. Вот примеры входных данных:
4 5 4 3 1 5 5 4 1
5 3 4 5 6 2 1 4 3 1 1 4 8 5 4 3
2 2 2 2 1 2 2 1 2 2 1 2
Для приведённых выше данных, результат функции программы должен быть следующим:
2
7
0

Ответ

Возьмем две матрицы: исходную, обозначим ее I. И рабочую, такого же размера как исходная, но заполненную максимально возможным теоретическим значением уровня (я взял с запасом 10000), обозначим ее W. Далее обходим рекурсивно все поле, последовательно начиная с каждой крайней клетки острова. Рекурсивная функция на вход принимает координаты обрабатываемой клетки и текущий уровень воды. Если полученный текущий уровень ниже, чем изначальная высота клетки (берем из I) то принимаем текущий уровень равным высоте клетки. Таким образом мы получаем тот уровень, до которого может подняться вода у всех соседних клеток, если их высота ниже. В рабочей же матрице мы фиксируем минимальный уровень соседей, т.е. максимально возможный уровень для данной клетки. Напомню, изначально мы его приняли за 10000. Так вот, если уровень в рабочей матрице для клетки оказался выше, чем текущий уровень то принимаем его равным текущему. Таким образом мы понижаем уровень до минимально возможного при проходе через всех соседей. И еще одно важное правило: если текущий уровень оказался больше, чем уже зафиксированный в рабочей матрице то рекурсивный обход тут же прекращаем. Раз в W уровень ниже, значит мы уже приходили на эту клетку с клеток с более низким стоком и проверять дальше соседей уже нет смысла, мы там были и там максимум ниже.
Для ускорения работы можно обходить граничные клетки в порядке увеличения высоты. Тогда мы сходу зальем минимумами все доступные от них области. И при анализе от более высоких клеток повторно обходить эти области не будем.
Пример на perl
#!/usr/bin/perl use strict; use warnings;
my @I; # Исходная матрица my @W; # Рабочая матрица my ($MX,$MY); # Размеры матрицы while() { # Читаем исходую матрицу my @row=(); chomp; last if(!$_); push @row, $_ for split / +/; push @I, \@row; $MX=@row; $MY++; # Запоминаем размеры my @row2=(); # И заполняем начальными значениями рабочую push @row2,10000 for(1..$MX); push @W, \@row2; } $MX--; $MY--; # обходим все 4 стороны прямоугольника cell(0,$_,0) for(1..$MY); cell($MX,$_,0) for(1..$MY); cell($_,0,0) for(1..$MX); cell($_,$MY,0) for(1..$MX);
# Печать результирующей матрицы и расчет объема воды my $summ=0; my $y=0; for(@W) { $,=" "; print "@$_
"; for my $x(0..$MX) { $summ+=$W[$y][$x]-$I[$y][$x]; } $y++; }
print "RESULT = $summ
";
# Основная рабочая, рекурсивная функция sub cell { my($x, $y, $lev)=@_; return if($x<0 || $y<0 || $x>$MX || $y>$MY); # Проверяем выход за пределы поля return if($W[$y][$x]<=$lev); # Максимум клетки ниже или равен - мы тут были $lev=$I[$y][$x] if($lev < $I[$y][$x]); # Повышаем текущий уровень, если ниже изначального для клетки $W[$y][$x]=$lev; # Устанавливаем текущий максимум cell($x-1,$y,$lev); # И обходим всех 4х соседей рекурсивно cell($x+1,$y,$lev); cell($x,$y-1,$lev); cell($x,$y+1,$lev); }