[USACO19OPEN]Valleys P

题目描述

Bessie喜欢观光,而今天她正在寻找景色优美的山谷。 她感兴趣的是一个 $ N \times N $ 的方阵,其中每个格子都有一个高度。所有在此正方形方阵之外的格子的高度可以被看作是无限大。 山谷指的是一块连续、不含洞的一块区域,并且每个相邻的包围该区域的格子都高于这块区域中的所有格子。 更形式化地说: * 一组格子被称作是“沿边相邻的”,如果可以从其中任意一个格子出发,经过一些沿上、下、左、右方向的移动,到达其中所有其他格子。 * 一组格子被称作是“沿点相邻的”,如果可以从其中任意一个格子出发,经过一些沿上、下、左、右、对角线方向的移动,到达其中所有其他格子。 * 一个“区域”指的是一组非空并且沿边相邻的格子。 * 一个区域被称作是“有洞的”,如果这个区域的补集(包括在 $ N \times N $ 方阵之外的无限高格子)不是沿点相邻的。 * 区域的“边界”指的是所有与该区域内的某个格子正交相邻(上、下、左、右),但本身不在该区域内的格子。 * 一个“山谷”指的是某个非有洞区域,满足区域内的任意格子的高度低于该区域边界上任意格子的高度。 Bessie的目标是求出所有山谷的大小之和。 ### 一些例子 这是一个区域: ``` oo. ooo ..o ``` 这不是一个区域(中间的格子和右下角的格子不沿边相邻): ``` oo. oo. ..o ``` 这是一个非有洞区域: ``` ooo o.. o.. ``` 这是一个有洞的区域(“甜甜圈”中间的格子与区域外的格子不沿点相邻): ``` ooo o.o ooo ``` 这是另一个非有洞区域(中间的格子与右下角的格子沿点相邻): ``` ooo o.o oo. ```

输入输出格式

输入格式


输入的第一行包含 $ N $ ,其中 $ 1 \leq N \leq 750 $ 。 以下 $ N $ 行每行包含 $ N $ 个整数,为方阵每个格子的高度。所有高度 $ h $ 满足 $ 1 \leq h \leq 10^6 $ 。所有高度均为不同的整数。

输出格式


输出一个整数,为所有山谷的大小之和。

输入输出样例

输入样例 #1

3
1 10 2
20 100 30
3 11 50

输出样例 #1

30

说明

在这个例子中,有三个大小为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。 ### 子任务 对于至少19%的测试数据, $ N \leq 100 $ 。