|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||2||2||2||100.000%|
Bessie likes sightseeing, and today she is looking for scenic valleys.
Of interest is an $N \times 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.
Bessie's goal is to determine the sum of the sizes of all valleys.
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.
First line contains integer $N$, where $1 \le N \le 750$.
Next $N$ lines each contain $N$ integers, the heights of the cells of the grid. Each height $h$ will satisfy $1 \le h \le 10^6$. Every height will be a distinct integer.
In at least 19% of the test cases, it is further guaranteed that $N \leq 100$.
Output a single integer, the sum of the sizes of all valleys.
3 1 10 2 20 100 30 3 11 50
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.