Rain on a hill
Count the cells where rain could run down to both coasts, by working backwards uphill from each coast. About 14 minutes.
Search backwards
A rectangular island has heights. Rain flows from a cell to a neighbour that is the same height or lower. The top and left edges touch the first coast, and the bottom and right edges touch the second. Which cells can send rain to both?
Asking it forwards from every cell means a search per cell. Flip it around. Start at the first coast's edge cells and walk uphill, to neighbours that are the same height or higher: every cell you reach can send water to that coast. Do the same from the second coast, and count the cells in both results.
- first_coast
- 9
Climb from the top and left edges. Every one of the 9 cells can send rain to the first coast.
Why climb from the coast instead of simulating the rain from every cell?
- ATwo climbs cover all cells, instead of one search per cell
- BWater flows uphill
- CIt gives a different answer but is easier
Show the answer
Two climbs cover all cells, instead of one search per cell. Each climb visits every cell at most once.
Rain to both coasts
heights is a grid of whole numbers giving the height of each cell. Rain on a cell flows to any neighbouring cell (up, down, left or right) whose height is the same or lower. The first coast touches the top row and the left column. The second coast touches the bottom row and the right column. Rain on a cell reaches a coast if it can flow, step by step, to a cell on that coast's edges. Return how many cells can send rain to both coasts.
heights = [[1, 2, 2], [3, 2, 3], [2, 4, 5]] → 8
1 ≤ rows, columns ≤ 20 · 0 ≤ height ≤ 100