Trapping Rain Water in a 2D Elevation Map

Problem Statement:

You are given an m x n grid representing a 2D elevation map where each cell denotes the height at that particular location. After a heavy rain, water may be trapped in the depressions of this map. Your task is to compute the total volume of water that can be trapped.

For each cell, the water that can be trapped is determined by the minimum height of the surrounding barrier cells minus the height of the cell itself, if this difference is positive. In mathematical terms, the water trapped at a cell is given by:

$$water_{cell} = \max(0, h_{boundary} - h_{cell})$$

where \(h_{boundary}\) is the minimum height among all adjacent boundary cells that have been reached from the outer border. The overall volume of trapped water is the sum of water in every cell.

Use an efficient algorithm (e.g., utilizing a min-heap and BFS) to solve the problem.

inputFormat

The first line contains two integers m and n representing the number of rows and columns of the elevation map.

The next m lines each contain n space-separated integers indicating the elevation of each cell.

outputFormat

Output a single integer representing the total volume of water that can be trapped on the map.

## sample

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

4