Trapping Rainwater in a 2D Grid

Given an m × n grid representing the height map of an area, your task is to compute the maximum amount of rainwater that can be trapped after a heavy downpour. Each cell in the grid has an elevation, and water will be trapped between cells, similar to how water might accumulate in low-lying areas. This problem can be modeled using a priority queue (min‐heap), and the water trapped at any cell is determined by the difference between the minimum boundary height and the cell's elevation. Formally, if the water level is \( L \) and the cell height is \( h_{i,j} \), then the water trapped on that cell is \( \max(0, L - h_{i,j}) \).

The grid is surrounded by boundaries which do not allow water to escape. Your solution should read the grid from standard input and output the total trapped water to standard output.

inputFormat

The first line contains two integers \( m \) and \( n \) separated by a space, where \( m \) is the number of rows and \( n \) is the number of columns in the grid. This is followed by \( m \) lines, each containing \( n \) space-separated integers representing the elevation of each cell.

Example:

3 6
1 4 3 1 3 2
3 2 1 3 2 4
2 3 3 2 3 1

outputFormat

Output a single integer: the total amount of rainwater that can be trapped in the given grid.

Example:

4

3 6
1 4 3 1 3 2
3 2 1 3 2 4
2 3 3 2 3 1

4