Rainwater Trapping on Uneven Terrain

Given an N × M grid representing a plot of land, where each cell has an area of one square inch and a height value in inches, determine the maximum volume of water (in cubic inches) that can be trapped after a heavy rain. The cell in the i-th row and j-th column is denoted as \(P(i,j)\) and its height is \(H(i,j)\).

After a heavy rain, water accumulates in the lower areas. The water that can be trapped at a cell depends on the minimum boundary height that can contain the water. More formally, if water is able to be contained, the trapped volume in that cell is:

[ \text{water}(i,j) = \max\Big(0, \min(\text{boundary heights}) - H(i,j)\Big) ]

Compute the total volume of water that can be trapped based on the given grid.

The grid is represented as:

[ \text{Grid} = \begin{bmatrix} H(1,1) & H(1,2) & \cdots & H(1,M) \ H(2,1) & H(2,2) & \cdots & H(2,M) \ \vdots & \vdots & \ddots & \vdots \ H(N,1) & H(N,2) & \cdots & H(N,M) \end{bmatrix} ]

inputFormat

The first line contains two integers N and M which denote the number of rows and columns, respectively.

Then follow N lines, each containing M integers, where each integer represents the height \(H(i,j)\) in inches of the cell.

outputFormat

Output a single integer representing the maximum volume of water (in cubic inches) that can be trapped.

sample

3 3
3 3 3
3 1 3
3 3 3

2