Задача про стоки, Паскаль

[Вива]

Задача про стоки, Паскаль

Стоки
Карту местности условно разбили на квадраты, и посчитали среднюю высоту над уровнем моря для каждого квадрата.
Когда идет дождь, вода равномерно выпадает на все квадраты. Если один из четырех соседних с данным квадратом квадратов имеет меньшую высоту над уровнем моря, то вода с текущего квадрата стекает туда (и, если есть возможность, то дальше), если же все соседние квадраты имеют большую высоту, то вода скапливается в этом квадрате.
Разрешается в некоторых квадратах построить водостоки. Когда на каком-то квадрате строят водосток, то вся вода, которая раньше скапливалась в этом квадрате, будет утекать в водосток.
Если есть группа квадратов, имеющих одинаковую высоту и образующих связную область, то если хотя бы рядом с одним из этих квадратов есть квадрат, имеющий меньшую высоту, то вся вода утекает туда, если же такого квадрата нет, то вода стоит во всех этих квадратах. При этом достаточно построить водосток в любом из этих квадратов, и вся вода с них будет утекать в этот водосток.
Требуется определить, какое минимальное количество водостоков нужно построить, чтобы после дождя вся вода утекала в водостоки.
Формат входных данных
Во входном файле записаны сначала числа N и M, задающие размеры карты — натуральные числа, не превышающие 100. Далее идет N строк, по M чисел в каждой, задающих высоту квадратов карты над уровнем моря. Высота задается натуральным числом, не превышающим 10000. Считается, что квадраты, расположенные за пределами карты, имеют высоту 10001 (то есть вода никогда не утекает за пределы карты).
Формат выходных данных
В выходной файл выведите минимальное количество водостоков, которое необходимо построить.

 

[Вива]

Примечание к задаче

Это задача на рекурсивный алгоритм. Хотя задача имеет большую вычислительную сложность, решение довольно компактное за счёт применения рекурсивной процедуры.

p – массив, высотой [n,m], по краям добавляем по ряду, поэтому [0..n+1, 0..m+1].
s – линейный массив 1+..n*m, если стока нет s=0, сток есть s=1.
а – массив меток, рассмотрели квадрат или нет. 0 – не смотрели, k – смотрели.
В рекурсивной процедуре onl просматриваем для каждой клетки наличие стоков во всех четырёх сторонах [x-1,y], [x+1,y], [x,y-1], [x,y+1]. Если уровень одинаков, то вызываем процедуру для соседней клетки.
Затем просматриваем массив s, считываем нули и выводим кол-во стоков