시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 62 | 27 | 23 | 52.273% |
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.
More formally:
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.
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
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.