Долины
Долины
Бесси любит осматривать достопримечательности, и сегодня она ищет живописные долины.
Ее интересует сетка n * n ячеек, где каждая ячейка имеет высоту. Можно считать, что каждая ячейка за пределами этой квадратной сетки имеет бесконечную высоту.
Долина - это область сетки, которая является смежной, не имеет дыр и такова, что каждая ячейка, непосредственно окружающая ее, находится выше всех ячеек в этом регионе.
Более формально:
Набор ячеек называется "реберно-смежным", если можно добраться до любой ячейки набора из любой другой последовательностью движений вверх, вниз, влево или вправо.
Набор ячеек называется "точечно-смежным", если можно добраться до любой ячейки набора из любой другой последовательностью движений вверх, вниз, влево, вправо или по диагонали.
"Регион" - это непустой набор прилегающих друг к другу реберно-смежных ячеек.
Регион называется "дырявым" если его дополнение (которое включает и бесконечные ячейки за пределами сетки n * n) не является точечно-смежным.
"Граница" области - это набор ячеек, ортогонально смежных (вверх, вниз, влево или вправо) с некоторой ячейкой в регионе, но не находящихся в самой области.
"Долина" - это любая область без дыр, в которой каждая ячейка имеет высоту ниже, чем каждая ячейка на границе области.
Задача Бесси - определить сумму размеров всех долин.
Примеры
Это регион:
oo.
ooo
..o
Это не регион (средняя ячейка и нижняя правая ячейка не являются смежными по краям):
oo.
oo.
..o
Это регион без дыр:
ooo
o..
o..
Это область с дыркой (отдельная ячейка в форме "бублика" не является точечно-смежной с "внешней стороной" области):
ooo
o.o
ooo
Это еще одна область без дыр (ячейка в центре точечно примыкает к ячейке в правом нижнем углу):
ooo
o.o
oo.
Входные данные
Первая строка содержит целое число n (1 ≤ n ≤ 750). Каждая из следующих n строк содержит n целых чисел - высоту ячеек сетки. Каждая высота h удовлетворяет условию 1 ≤ h ≤ 10^6
. Все высоты - различные целые числа.
Выходные данные
Выведите единственное целое число - сумму размеров всех долин.
Пример
В этом примере три долины размера 1:
o.o
...
o..
Одна долина размера 2:
...
...
oo.
Одна долина размера 3:
ooo
...
...
Одна долина размера 6:
ooo
o..
oo.
Одна долина размера 7:
ooo
o.o
oo.
Одна долина размера 9:
ooo
ooo
ooo
Таким образом ответ 1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30.
Пример
3 1 10 2 20 100 30 3 11 50
30