Compute rainwater accumulation on a height grid

Mountain Rainfall Accumulation

You are given an m x n 2D integer grid elevation, where elevation[r][c] is the terrain height at cell (r, c).

Assume 1 unit of rain falls on each cell (uniformly). Water from a cell flows downhill by repeatedly moving to a neighboring cell with strictly lower elevation until it reaches a local minimum (a cell that has no strictly lower neighbor).

• Neighbors are the 4 orthogonal cells: up, down, left, right (when in bounds).
• From a cell, water moves to the neighbor that represents the steepest descent . You may implement this as moving to the neighbor with the minimum elevation among all strictly lower neighbors.
• If there are multiple equally-steep choices (ties), you may break ties arbitrarily , so multiple different correct outputs may exist.

Task

Return an m x n integer grid accum where:

• accum[r][c] equals the total number of rain units that eventually end at cell (r, c) (including the unit that fell on (r, c) itself if it is a sink).
• All non-sink cells should have 0 in accum (since they do not collect water permanently).

Example

Input

[
  [3, 3, 1, -1],
  [2, 3, 3,  1],
  [0, 1, 3,  3]
]

One valid output

[
  [0, 0, 0, 6],
  [0, 0, 0, 0],
  [6, 0, 0, 0]
]

Another valid output (due to tie-breaking)

[
  [0, 0, 0, 7],
  [0, 0, 0, 0],
  [5, 0, 0, 0]
]

(There are 12 cells total, so the sum of all values in accum should be 12.)