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喜歡觀光，而今天她正在尋找景色優(yōu)美的山谷。

她感興趣的是一個(gè)N×NN×N的方陣，其中每個(gè)格子都有一個(gè)高度。所有在此正方形方陣之外的格子的高度可以被看作是無限大。

山谷指的是一塊連續(xù)、不含洞的一塊區(qū)域，并且每個(gè)相鄰的包圍該區(qū)域的格子都高于這塊區(qū)域中的所有格子。

更形式化地說：

一組格子被稱作是“沿邊相鄰的”，如果可以從其中任意一個(gè)格子出發(fā)，經(jīng)過一些沿上、下、左、右方向的移動，到達(dá)其中所有其他格子。
一組格子被稱作是“沿點(diǎn)相鄰的”，如果可以從其中任意一個(gè)格子出發(fā)，經(jīng)過一些沿上、下、左、右、對角線方向的移動，到達(dá)其中所有其他格子。
一個(gè)“區(qū)域”指的是一組非空并且沿邊相鄰的格子。
一個(gè)區(qū)域被稱作是“有洞的”，如果這個(gè)區(qū)域的補(bǔ)集（包括在N×NN×N方陣之外的無限高格子）不是沿點(diǎn)相鄰的。
區(qū)域的“邊界”指的是所有與該區(qū)域內(nèi)的某個(gè)格子正交相鄰（上、下、左、右），但本身不在該區(qū)域內(nèi)的格子。
一個(gè)“山谷”指的是某個(gè)非有洞區(qū)域，滿足區(qū)域內(nèi)的任意格子的高度低于該區(qū)域邊界上任意格子的高度。

Bessie的目標(biāo)是求出所有山谷的大小之和。

一些例子

這是一個(gè)區(qū)域：

oo.
ooo
..o

這不是一個(gè)區(qū)域（中間的格子和右下角的格子不沿邊相鄰）：

oo.
oo.
..o

這是一個(gè)非有洞區(qū)域：

ooo
o..
o..

這是一個(gè)有洞的區(qū)域（“甜甜圈”中間的格子與區(qū)域外的格子不沿點(diǎn)相鄰）：

ooo
o.o
ooo

這是另一個(gè)非有洞區(qū)域（中間的格子與右下角的格子沿點(diǎn)相鄰）：

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

輸入的第一行包含NN，其中1≤N≤7501≤N≤750。以下NN行每行包含NN個(gè)整數(shù)，為方陣每個(gè)格子的高度。所有高度hh滿足1≤h≤1061≤h≤106。所有高度均為不同的整數(shù)。

對于至少19%的測試數(shù)據(jù)，額外保證N≤100N≤100。

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

輸出一個(gè)整數(shù)，為所有山谷的大小之和。

輸入樣例：
3
1 10 2
20 100 30
3 11 50

輸出樣例：
30

在這個(gè)例子中，有三個(gè)大小為1的山谷：

o.o
...
o..

一個(gè)大小為2的山谷：

...
...
oo.

一個(gè)大小為3的山谷：

ooo
...
...

一個(gè)大小為6的山谷：

ooo
o..
oo.

一個(gè)大小為7的山谷：

ooo
o.o
oo.

以及一個(gè)大小為9的山谷：

ooo
ooo
ooo

所以，答案為1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30。

供題：Travis Hance