200 Max Water Trapped II (Lai)

Given a non-negative integer 2D array representing the heights of bars in a matrix. Suppose each bar has length and width of 1. Find the largest amount of water that can be trapped in the matrix. The water can flow into a neighboring bar if the neighboring bar's height is smaller than the water's height. Each bar has 4 neighboring bars to the left, right, up and down side.

Assumptions

• The given matrix is not null and has size of M * N, where M > 0 and N > 0, all the values are non-negative integers in the matrix.

Examples

{ { 2, 3, 4, 2 },

{ 3, 1, 2, 3 },

{ 4, 3, 5, 4 } }

the amount of water can be trapped is 3,

at position (1, 1) there is 2 units of water trapped,

at position (1, 2) there is 1 unit of water trapped.

Solution: