Valleys

题目描述

Bessie 喜欢观光，今天她正在寻找风景优美的山谷。

我们关注一个 $N \times N$ 的网格，每个格子都有一个高度。 可以认为这个正方形网格之外的所有格子高度为无穷大。

一个山谷（valley）是该网格中的一个区域，它需要是连通的、没有洞，并且其周围紧贴着它的每个格子都比区域内所有格子更高。 更正式地说：

若一个格子集合中，任意两格都可以通过一系列上下左右的移动互相到达，则称该集合“边相邻连通”（edgewise-contiguous）。 若一个格子集合中，任意两格都可以通过一系列上下、下、左、右或对角线移动互相到达，则称该集合“点相邻连通”（pointwise-contiguous）。 “区域”（region）是一个非空的边相邻连通格子集合。 若某个区域的补集（包括 $N \times N$ 网格外的无穷多个格子）不是点相邻连通的，则称该区域“有洞”（holey）。 一个区域的“边界”（border）是指与区域中某个格子在正交方向（上、下、左、右）相邻、但不属于该区域的所有格子集合。 “山谷”（valley）是任意一个无洞区域，并且满足：区域内每个格子的高度都小于该区域边界上每个格子的高度。

Bessie 的目标是计算所有山谷大小之和。

示例 这是一个区域： oo. ooo ..o 这是一个不是区域的例子（中间格子与右下角格子不是边相邻连通的）： oo. oo. ..o 这是一个无洞区域： ooo o.. o.. 这是一个有洞区域（“甜甜圈”形状内部的单个格子与区域外部不是点相邻连通的）： ooo o.o ooo 这是另一个无洞区域（中间的单个格子与右下角的格子是点相邻连通的）： ooo o.o oo.

输入格式

第一行包含整数 $N$，其中 $1 \le N \le 750$。 接下来 $N$ 行，每行包含 $N$ 个整数，表示网格各格子的高度。 每个高度 $h$ 满足 $1 \le h \le 10^6$。所有高度互不相同。 在至少 19% 的测试用例中，额外保证 $N \leq 100$。

输出格式

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

3
1 10 2
20 100 30
3 11 50

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。 题目鸣谢：Travis Hance

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum