Trapping Rain Water II

Each entry of heightMap is the elevation of a cell with unit area. After rain, water may collect above low cells, but it can flow between cells sharing an edge and escape across the outer boundary. Return the total volume of water retained when no more water can drain away. Diagonal contact alone does not provide a drainage route.

Hatching marks cells that hold water. The elevation diagram shows water as hatched volume above the solid columns.

Example 1:

Input: heightMap = [[5,5,5],[5,1,5],[5,5,5]]

Output: 4

Explanation: The center cell has height 1 and is enclosed by height-5 cells. It holds water to height 5, for a volume of 5 - 1 = 4.

Example 2:

Input: heightMap = [[5,0,5],[5,1,5],[5,5,5]]

Output: 0

Explanation: The center cell has an edge-connected route to the height-0 cell on the top boundary. Water escapes through that outlet, so none is retained.

Example 3:

Input: heightMap = [[4,0,4]]

Output: 0

Explanation: Every cell lies on the outer boundary because the map has only one row. Water drains sideways out of the map, so the middle cell cannot hold water.

Constraints:

• Each dimension is between 1 and 200; all rows have equal length.
• 0 <= heightMap[i][j] <= 20000