Rainwater on a Terrain

Difficulty: 2200 6000 ms 128 MB

bfs heap

A 2-D height map is given. After heavy rain, water pools in basins but drains off the grid's border. Print the total volume of trapped water.

Input: the first line has N and M; the next N lines form the height grid.

Output: the total trapped water volume.

Constraints:

• 1 ≤ N, M ≤ 500
• 0 ≤ height ≤ 10⁴

Sample Tests

3 3
5 5 5
5 1 5
5 5 5

4

1 5
1 2 3 4 5

0

Read the Editorial