A6128. 「USACO 2019 US Open Platinum」Valleys
编程题
NOI/NOI+/CTSC
知识点
题目描述
**题目来自 [USACO 2019 US Open Contest, Platinum](http://usaco.org/index.php?page=open19results) Problem 3. [Valleys](http://usaco.org/index.php?page=viewproblem2&cpid=950)**
Bessie 喜欢观光，而今天她正在寻找景色优美的山谷。
她感兴趣的是一个 $N\times N$ 的方阵，其中每个格子都有一个高度。所有在此正方形方阵之外的格子的高度可以被看作是无限大。
山谷指的是一块连续、不含洞的一块区域，并且每个相邻的包围该区域的格子都高于这块区域中的所有格子。
更形式化地说：
- 一组格子被称作是「沿边相邻的」，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右方向的移动，到达其中所有其他格子。
- 一组格子被称作是「沿点相邻的」，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右、对角线方向的移动，到达其中所有其他格子。
- 一个「区域」指的是一组非空并且沿边相邻的格子。
- 一个区域被称作是「有洞的」，如果这个区域的补集（包括在 $N\times N$ 方阵之外的无限高格子）不是沿点相邻的。
- 区域的「边界」指的是所有与该区域内的某个格子正交相邻（上、下、左、右），但本身不在该区域内的格子。
- 一个「山谷」指的是某个非有洞区域，满足区域内的任意格子的高度低于该区域边界上任意格子的高度。
Bessie 的目标是求出所有山谷的大小之和。
Bessie 喜欢观光，而今天她正在寻找景色优美的山谷。
她感兴趣的是一个 $N\times N$ 的方阵，其中每个格子都有一个高度。所有在此正方形方阵之外的格子的高度可以被看作是无限大。
山谷指的是一块连续、不含洞的一块区域，并且每个相邻的包围该区域的格子都高于这块区域中的所有格子。
更形式化地说：
- 一组格子被称作是「沿边相邻的」，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右方向的移动，到达其中所有其他格子。
- 一组格子被称作是「沿点相邻的」，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右、对角线方向的移动，到达其中所有其他格子。
- 一个「区域」指的是一组非空并且沿边相邻的格子。
- 一个区域被称作是「有洞的」，如果这个区域的补集（包括在 $N\times N$ 方阵之外的无限高格子）不是沿点相邻的。
- 区域的「边界」指的是所有与该区域内的某个格子正交相邻（上、下、左、右），但本身不在该区域内的格子。
- 一个「山谷」指的是某个非有洞区域，满足区域内的任意格子的高度低于该区域边界上任意格子的高度。
Bessie 的目标是求出所有山谷的大小之和。
输入格式
输入的第一行包含 $N$，其中 $1\le N\le 750$。
以下 $N$ 行每行包含 $N$ 个整数，为方阵每个格子的高度。所有高度 $h$ 满足 $1\le h\le 10^6$。所有高度均为不同的整数。
以下 $N$ 行每行包含 $N$ 个整数，为方阵每个格子的高度。所有高度 $h$ 满足 $1\le h\le 10^6$。所有高度均为不同的整数。
输出格式
输出一个整数，为所有山谷的大小之和。
输入输出样例
输入 #1
3 1 10 2 20 100 30 3 11 50
输出 #1
30
说明/提示
对于至少 $19\%$ 的测试数据，额外保证 $N\le 100$。