We want to find the amount of water at each square, and sum them together.

The trick here is that there's always a square where we can find the water level (the height the water can rise to) immediately. If you pick the lowest square on the border, then you immediately know all the neighbors' water levels.

You can repeat this idea to find the water level at every square - pick the smallest square on the border, find the water level of its neighbors, and then add the neighbors to the border and repeat.

Once you know the water level at a square, you can get the amount of water there by just subtracting off the height of that square:

The max(0, ...) is just there to keep it from going negative since you can't have negative water at a square.

Now we can code this up. We're going to constantly take the minimum value on the border. We can do this optimally with a Heap, since a lot of those values will be the same each time. The full algorithm is:

Time Complexity $O((m\cdot n) \log (m\cdot n))$. The Heap grows to the size of the border, which can get very distorted and is roughly of size $m\cdot n$. We pop the Heap at every square doing a $\log (m\cdot n)$ operation, and there are $m\cdot n$ squares. The Heap initializiation only takes $O(m \cdot n)$.

Space Complexity $O(m\cdot n)$ for the Heap.