Беси рассматривает решётку \(N \times N\) ячеек, где каждая ячейка имеет высоту.
Каждая ячейка вне этой решётки считается имеющей бесконечную высоту.
Долиной называется регион решётки, непрерывный, без дыр, и такой, что
каждую ячейку непосредственно окружают ячейки, каждая из которых выше чем все ячейки региона.
Более формально:
- Множество ячеек называется "смежными с торцевой", если можно достичь
любую ячейку этого множества из любой двигаясь вправо, влево, вверх, вниз.
- Множество ячеек называется "точечно-смежным" если можно из любой ячейки
множества достичь любой другой ячейки множества, двигаясь, влево, вправо, вверх, вниз
или по диагонали.
- Регион - это непустое множество ячеек "смежных с торцевой".
- Регион называется дырявым, если дополнение региона (которое включает
бесконечные ячейки вне решётки) не является "точечно-смежным".
- Граница региона - это множество ячеек, ортогонально соседних
(вверх, вниз, влево, вправо) к некоторой ячейке региона, но не принадлежащих региону.
- "Долина" это любой недырявый регион, в котором каждая ячейка имеет высоту
ниже чем каждая ячейка границы долины.
Цель Беси - определить сумму размеров всех долин.
Примеры
Это регион:
oo.
ooo
..o
Это не регион (средняя ячейка и нижняя правая ячейка не являются "смежными с торцевой"):
oo.
oo.
..o
Это регион без дыр:
ooo
o..
o..
Это дырявый регион (одна ячейка внутри):
ooo
o.o
ooo
Это другой недырявый регион (центральная ячейка является точечно-смежной
с ячейкой в правом нижнем углу):
ooo
o.o
oo.
ФОРМАТ ВВОДА (файл valleys.in):
Первая строка содержит целое число
\(N\), где
\(1 \le N \le 750\).
Каждая из следующих \(N\) строк содержит \(N\) целых чисел - высоты ячеек решётки.
Каждая высота \(h\) удовлетворяет \(1 \le h \le 10^6\). Все высоты различны.
в 19% тестов гарантируется \(N \leq 100\).
ФОРМАТ ВЫВОДА (файл valleys.out):
Выведите одно целое число, сумму размеров всех долин.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 10 2
20 100 30
3 11 50
|
30
|