For a matrix =
[ 5, 5, 5 ]
[ 5, 2, 3 ]
[ 6, 9, 8 ]
2-D elevation map will look like this
After the rain, a total of 1 unit volume of water gets trapped, and this 2-D elevation map will look like this
The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of each test case contains two space-separated integers ‘M’ and ‘N’ denoting the number of rows and columns in the matrix.
The next ‘M’ lines contain ‘N’ space-separated integers denoting the height of each cell.
For each test case, print a single integer denoting the volume of water that can be trapped.
Print the output of each test case in a separated line.
You don't need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 10
1 <= M,N <= 100
1 <= matrix[i][j] <= 10^3
Where ‘T’ is the number of test cases, ‘M’ and ‘N’ are the dimensions of the given matrix.
Matrix[i][j] is the height of the cell at the ‘i-th’ row and ‘j-th’ column.
Time Limit: 1 sec.
Now the water that can behold at least inside the cells will be equal to the minimum height of the boundary.
For eg if matrix = [ 8, 8, 8, 8 ]
[ 6, x, x, 8 ]
[ 6, x, x, 5 ]
[ 6, 8, 8, 8 ]
Now if any cell holds water > mat[ 2 ][ 3 ] then it can flow out. So if any of the cells have a height less than ‘5’ then it can trap utmost ‘5’ volume water in it.
We have to maintain this minimum border height also so that it can be determined what volume of water we can store.
So the basic idea is we will find the boundary cell having minimum height. If any of its neighbor cells have a height less than the minimum border height then it can store water = difference between the height of cells and minimum border height Otherwise all the neighboring cells will be considered as boundary cells.
We will take a priority queue that will store the cell positions based on the height of each cell.
Initially, we will visit all the boundary cells and put them in the queue.
Now the front element of the queue will give the cell a minimum height.
Now visit the neighbors of the boundary cell having minimum height. Push all the neighbors to queue. If any cell has a height smaller than this boundary cell then it can trap water = difference between heights of this cell and minimum border height.
Whenever a front element of the queue is popped out, if the cell has a height of more than the minimum border height, then we will update the minimum border height.
Algorithm: