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