P5423 [USACO19OPEN] Valleys P

Bessie likes sightseeing, and today she is looking for valleys with beautiful scenery. She is interested in an $N \times N$ square grid, where each cell has a height. The heights of all cells outside this square grid can be considered to be infinitely large. A valley is a connected, hole-free region such that every neighboring cell surrounding this region is higher than all cells in the region. More formally: * A set of cells is called “edge-connected” if, starting from any one of the cells, it is possible to reach all other cells in the set by moving some number of steps in the up, down, left, and right directions. * A set of cells is called “corner-connected” if, starting from any one of the cells, it is possible to reach all other cells in the set by moving some number of steps in the up, down, left, right, and diagonal directions. * A “region” is a non-empty set of edge-connected cells. * A region is called “with holes” if the complement of this region (including the infinitely high cells outside the $N \times N$ grid) is not corner-connected. * The “boundary” of a region is the set of all cells that are orthogonally adjacent (up, down, left, right) to some cell in the region, but are not themselves in the region. * A “valley” is a region without holes such that the height of every cell in the region is lower than the height of every cell on the region’s boundary. Bessie’s goal is to compute the sum of the sizes of all valleys. ### Some examples This is a region: ``` oo. ooo ..o ``` This is not a region (the middle cell and the bottom-right cell are not edge-connected): ``` oo. oo. ..o ``` This is a hole-free region: ``` ooo o.. o.. ``` This is a region with holes (the cell in the middle of the “donut” is not corner-connected to the outside of the region): ``` ooo o.o ooo ``` This is another hole-free region (the cell in the middle is corner-connected to the bottom-right cell): ``` ooo o.o oo. ```

The first line contains $N$, where $1 \leq N \leq 750$. The next $N$ lines each contain $N$ integers, the heights of the cells in the grid. All heights $h$ satisfy $1 \leq h \leq 10^6$. All heights are distinct integers.

Output one integer: the sum of the sizes of all valleys.

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 ``` So the answer is $1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30$. ### Subtasks For at least $19\%$ of the testdata, $N \leq 100$. Translated by ChatGPT 5