Finally, after a heavy storm, Antu's team is mapping how much rainwater pools across the city's uneven terrain grid, and needs the total trapped volume computed. Given an N×M grid of non-negative heights representing terrain, compute the total volume of rainwater trapped after rain (water is trapped in a cell if it's surrounded by higher or equal terrain in all directions, following boundary constraints). Use a min-heap based boundary expansion (similar to Dijkstra), O(NM log(NM)).
Input
Line1: N M. Next N lines: M integers each (heights).
Output
Total trapped water volume.
Constraints
1 ≤ N,M ≤ 200
Sample Input
3 6 1 4 3 1 3 2 3 2 1 3 2 4 2 3 3 2 3 1
Sample Output
4
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.