EduBrick

N. Водостоки

2000 мс · 256 МБ · всё или ничего

Карта разбита на квадраты, для каждого известна высота. Вода стекает из квадрата в соседний по стороне, если тот ниже. За пределами карты высота считается равной 1000110001, то есть наружу вода не утекает.

Если несколько соседних квадратов имеют одинаковую высоту, они образуют связную область — плато. Вода со всего плато утекает, если хотя бы у одного его квадрата есть более низкий сосед. Если такого соседа нет ни у одного, вода стоит на всём плато, и там нужен водосток — достаточно одного на плато.

Найдите наименьшее количество водостоков.

Задача целиком про то, что вершина — не квадрат, а плато. Разбейте карту на связные области одинаковой высоты обходом и посчитайте те, у которых нет ни одного соседа меньшей высоты. Их количество и есть ответ.

Формат ввода

Первая строка содержит числа NN и MM (1≤N,M≤1001 \le N, M \le 100).

Далее идут NN строк по MM чисел — высоты, натуральные и не больше 10410^4.

Формат вывода

Одно число — минимальное количество водостоков.

Примеры

ввод
4 4
1 2 4 1
2 4 4 4
1 4 3 2
1 2 3 2
вывод
4
ввод
1 5
1 1 1 1 1
вывод
1
Войдите, чтобы отправлять решения.