USACO 2019 US Open Contest, Platinum Problem 3. Valleys

Bessie likes sightseeing, and today she is looking for scenic valleys.

Of interest is an N×NN×N grid of cells, where each cell has a height. Every cell outside this square grid can be considered to have infinite height.

A valley is a region of this grid which is contiguous, has no holes, and is such that every cell immediately surrounding it is higher than all cells in the region.

More formally:

A set of cells is called "edgewise-contiguous" if one can reach any cell of the set from any other by a sequence of moves up, down, left, or right.
A set of cells is called "pointwise-contiguous" if one can reach any cell of the set from any other by a sequence of moves up, down, left, right, or diagonally.
A "region" is a non-empty edgewise-contiguous set of cells.
A region is called "holey" if the complement of the region (which includes the infinite cells outside the N×NN×N grid) is not pointwise-contiguous.
The "border" of a region is the set of cells orthogonally adjacent (up, down, left, or right) to some cell in the region, but which is not in the region itself.
A "valley" is any non-holey region such that every cell in the region has height lower than every cell on the region's border.

Bessie's goal is to determine the sum of the sizes of all valleys.

Examples

This is a region:

oo.
ooo
..o

This is not a region (the middle cell and the lower-right cell are not edgewise-contiguous):

oo.
oo.
..o

This is a non-holey region:

ooo
o..
o..

This is a holey region (the single cell within the "donut" shape is not pointwise-contiguous with the "outside" of the region):

ooo
o.o
ooo

This is another non-holey region (the single cell in the enter is pointwise-contiguous with the cell in the lower-right corner):

ooo
o.o
oo.
INPUT FORMAT (file valleys.in):

First line contains integer NN, where 1≤N≤7501≤N≤750.Next NN lines each contain NN integers, the heights of the cells of the grid. Each height hh will satisfy 1≤h≤1061≤h≤106. Every height will be a distinct integer.

In at least 19% of the test cases, it is further guaranteed that N≤100N≤100.

OUTPUT FORMAT (file valleys.out):

Output a single integer, the sum of the sizes of all valleys.

SAMPLE INPUT:
3
1 10 2
20 100 30
3 11 50

SAMPLE OUTPUT:
30

In this example, there are three valleys of size 1:

o.o
...
o..

One valley of size 2:

...
...
oo.

One valley of size 3:

ooo
...
...

One valley of size 6:

ooo
o..
oo.

One valley of size 7:

ooo
o.o
oo.

And one valley of size 9:

ooo
ooo
ooo

Thus, the answer is 1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30.

Problem credits: Travis Hance

中文版

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

她感兴趣的是一个N×NN×N的方阵，其中每个格子都有一个高度。所有在此正方形方阵之外的格子的高度可以被看作是无限大。

山谷指的是一块连续、不含洞的一块区域，并且每个相邻的包围该区域的格子都高于这块区域中的所有格子。

更形式化地说：

一组格子被称作是“沿边相邻的”，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右方向的移动，到达其中所有其他格子。
一组格子被称作是“沿点相邻的”，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右、对角线方向的移动，到达其中所有其他格子。
一个“区域”指的是一组非空并且沿边相邻的格子。
一个区域被称作是“有洞的”，如果这个区域的补集（包括在N×NN×N方阵之外的无限高格子）不是沿点相邻的。
区域的“边界”指的是所有与该区域内的某个格子正交相邻（上、下、左、右），但本身不在该区域内的格子。
一个“山谷”指的是某个非有洞区域，满足区域内的任意格子的高度低于该区域边界上任意格子的高度。

Bessie的目标是求出所有山谷的大小之和。

一些例子

这是一个区域：

oo.
ooo
..o

这不是一个区域（中间的格子和右下角的格子不沿边相邻）：

oo.
oo.
..o

这是一个非有洞区域：

ooo
o..
o..

这是一个有洞的区域（“甜甜圈”中间的格子与区域外的格子不沿点相邻）：

ooo
o.o
ooo

这是另一个非有洞区域（中间的格子与右下角的格子沿点相邻）：

ooo
o.o
oo.
输入格式（文件名：valleys.in）：

输入的第一行包含NN，其中1≤N≤7501≤N≤750。以下NN行每行包含NN个整数，为方阵每个格子的高度。所有高度hh满足1≤h≤1061≤h≤106。所有高度均为不同的整数。

对于至少19%的测试数据，额外保证N≤100N≤100。

输出格式（文件名：valleys.out）：

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

输入样例：
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