Rainwater on a Terrain — Solution & Editorial

Back to the Problem

Priority-queue flood from the border inward: always process the lowest boundary cell; a neighbour lower than the current water level traps (level − height), and its effective level becomes the max of its height and the current level.

Complexity: O(NM log(NM))

Watch out: 1-D trapping logic fails in 2-D — water escapes through the lowest surrounding wall, which the heap models.