Rain on a Height Map

A landscape is built from square columns of stone on a grid. heights is a list of rows, each a list of non-negative integers: the height of the column on that square. After heavy rain, water settles on top of the columns wherever it cannot run off. Water flows from a square to its neighbours up, down, left and right (not diagonally), and water that reaches the outer edge of the grid runs off the map.

Write trapped_rain(heights) that returns the total volume of water left standing, where one unit is the water above one square, one unit deep.

Examples

trapped_rain([[3, 3, 3],
              [3, 1, 3],
              [3, 3, 3]])         # returns 2
trapped_rain([[4, 4, 4, 4],
              [4, 1, 2, 4],
              [4, 4, 3, 4]])      # returns 3
trapped_rain([[1, 2, 3],
              [4, 5, 6]])         # returns 0

In the second example the pool spills over the 3 in the bottom row, so its surface stays at height 3: 2 units deep above the 1 and 1 unit deep above the 2. In the last, every square is on the edge, so nothing stays.

Constraints

• 1 to 200 rows and 1 to 200 columns.
• Heights are between 0 and 20,000.