|
Водостоки
(Время: 1 сек. Память: 16 Мб Сложность: 55%)
Карту местности условно разбили на квадраты, и посчитали среднюю высоту над уровнем моря для каждого квадрата.
Когда идет дождь, вода равномерно выпадает на все квадраты. Если один из четырех соседних с данным квадратом квадратов имеет меньшую высоту над уровнем моря, то вода с текущего квадрата стекает туда (и, если есть возможность, то дальше), если же все соседние квадраты имеют большую высоту, то вода скапливается в этом квадрате.
Разрешается в некоторых квадратах построить водостоки. Когда на каком-то квадрате строят водосток, то вся вода, которая раньше скапливалась в этом квадрате, будет утекать в водосток.
Если есть группа квадратов, имеющих одинаковую высоту и образующих связную область, то если хотя бы рядом с одним из этих квадратов есть квадрат, имеющий меньшую высоту, то вся вода утекает туда, если же такого квадрата нет, то вода стоит во всех этих квадратах. При этом достаточно построить водосток в любом из этих квадратов, и вся вода с них будет утекать в этот водосток.
Требуется определить, какое минимальное количество водостоков нужно построить, чтобы после дождя вся вода утекала в водостоки.
Входные данные
Во входном файле INPUT.TXT записаны сначала числа N и M, задающие размеры карты — натуральные числа, не превышающие 100. Далее, идет N строк, по M чисел в каждой, задающих высоту квадратов карты над уровнем моря. Высота задается натуральным числом, не превышающим 10000. Считается, что квадраты, расположенные за пределами карты, имеют высоту 10001 (то есть вода никогда не утекает за пределы карты).
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное количество водостоков, которое необходимо построить.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 5
1 2 3 1 10
1 4 3 10 10
1 5 5 5 5
6 6 6 6 6
| 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
