915. Water Held in a Basin

A grid of rows by cols cells gives the height of the ground at each cell. Rain falls until nothing more can be held. Water runs off the four outer edges of the grid and flows between cells that share a side, never diagonally.

Print the total volume of water held, where one unit of depth on one cell is one unit of volume.

``` 1 4 3 1 3 2 3 2 1 3 2 4 -> 4 2 3 3 2 3 1

9 9 9 9 9 0 0 9 -> 0 only two rows, so both zeros touch the edge ```

## What most people try first

The one-dimensional version has a clean answer: the water over a bar is the smaller of the tallest wall to its left and the tallest wall to its right, minus the bar. That is problem #170.

In two dimensions it is simply false. Water does not escape along a row or a column; it escapes along ANY path to the border, and the level at a cell is decided by the lowest such path, not by four directional maxima. A basin can be sealed on all four compass lines and still leak through a diagonal staircase of low cells.

Repeatedly relaxing every cell against its neighbours until nothing changes is correct and is what the oracle for this problem does, and it costs O((rows * cols)^2) in the worst case: 8.1 * 10^9 at the limits.

## The method: flood inwards from the lowest point of the wall

Think of the border as a wall of known heights and push inwards.

mark every border cell visited and push (its height, row, col) into a MIN-heap total = 0 while the heap is not empty: (level, r, c) = pop the smallest for each unvisited neighbour (x, y): mark it visited if height[x][y] < level: total = total + (level - height[x][y]) push (max(level, height[x][y]), x, y)

The key pushed for a neighbour is not its own height: it is the WATER LEVEL that reaches it, which is the larger of its height and the level it was reached from. That derived key is the whole idea.

## Why it is correct

Process the cells in increasing order of final water level, which is what the min-heap enforces.

Claim: when a cell is popped, its key is its true final water level. The level at a cell is the minimum, over all paths from that cell to the border, of the largest height along the path. The algorithm is Dijkstra's with "sum along the path" replaced by "maximum along the path", and the same argument applies: because the key of a neighbour is never smaller than the key of the cell it was reached from, keys are popped in non-decreasing order, so the first time a cell is reached it is reached by the path with the smallest maximum.

Given the level, the water standing on a cell is level - height when that is positive, and the total is the sum over all cells.

A cell on the border has level equal to its own height, so it holds nothing, which is what "water runs off the edge" means.

## The boundary that breaks a careless implementation

Mark a cell visited when it is PUSHED, not when it is popped. Marking on pop lets the same cell enter the heap from several neighbours, and the extra copies carry larger levels, so the water is counted more than once.

A grid with fewer than three rows or fewer than three columns holds nothing at all, because every cell is on the border. The code above handles that without a special case, but only if the border is pushed correctly, and a loop that treats row 0 and row rows-1 as distinct crashes when rows == 1.

Duplicate pushes of the same border cell, when the grid is a single row or column, must not double count. Marking on push covers this too.

## Overflow

Depth on one cell reaches 10^9, and with 300 * 300 cells the total reaches 9 * 10^13. The declared test with a five by five grid of 10^9 walls around a three by three pit of zeros already totals 9 * 10^9, which a 32-bit accumulator reports as 410065408. The running total must be 64-bit; the individual heights and levels fit in 32 bits.

## Related problems

Problem #170 is the one-dimensional original and #846 asks for the water over each individual bar. Both are solved without a heap because in one dimension the escape routes are only two, left and right, and can be precomputed. Two dimensions removes that, and what replaces it is a shortest path where the cost of a route is its maximum rather than its sum, exactly the measure problem #1645 introduces on a graph.

## Cost

Time O(rows * cols * log(rows * cols)). Space O(rows * cols).

Constraints - `1 ≤ rows ≤ 300` - `1 ≤ cols ≤ 300` - `0 ≤ height ≤ 10^9`