Trapping Rain Water in a 2D Grid

You are given an n x m grid representing a terrain, where each cell contains a non-negative integer that represents its height. When it rains, water will be trapped by the surrounding barriers. Your task is to compute how much water is trapped after the rain has settled.

The problem can be modeled using a min-heap and a breadth-first search approach. In particular, you may think of the grid as a container and the trapped water at any cell is determined by the difference between the height of the cell and the minimum height of its boundary (which may have been raised by previous water accumulation). Formally, let \(grid[i][j]\) denote the height at cell \((i,j)\). Then the water trapped in that cell is given by:

\( \max(0, B - grid[i][j]) \)

where \(B\) is the minimum boundary height around cell \((i,j)\) that can hold the water.

Input will be provided via standard input and output must be printed to standard output.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\), indicating the number of rows and columns respectively. The following \(n\) lines each contain \(m\) space-separated integers, representing the heights of the grid cells.

Example:

4 4
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

outputFormat

Output a single integer representing the total amount of water trapped after the rain.

Example Output:

4

## sample

4 4
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

4