Find all cells reachable by downhill flow

Problem

You are given an m x n grid heights, where heights[r][c] is the elevation of cell (r, c).

A drop of water is placed at a starting cell start = (sr, sc). From a cell, water may flow to any of its 4-directional neighbors (up/down/left/right) only if the neighbor has strictly lower height than the current cell.

A cell is considered wet if water can reach it by repeatedly flowing according to the rule above (including the start cell).

Task

Return the list (or set) of all wet cells.

Input

• heights: 2D integer array of size m x n
• start: two integers (sr, sc) with 0 <= sr < m, 0 <= sc < n

Output

• All coordinates (r, c) that become wet.

Notes / Constraints

• You may return cells in any order.
• Assume m, n can be up to a few thousand (so your approach should be near-linear in grid size in the worst case).
• Heights can be any integers (not necessarily unique).

Find all cells reachable by downhill flow

You are given an m x n grid heights, where heights[r][c] is the elevation of cell (r, c).

A drop of water is placed at a starting cell start = (sr, sc). From a cell, water may flow to any of its 4-directional neighbors (up, down, left, right) only if the neighbor has strictly lower height than the current cell.

A cell is considered wet if water can reach it by repeatedly flowing according to this rule (the start cell is always wet).

Return the list of all wet cells as [r, c] pairs. You may return them in any order; for these tests, return them sorted in ascending (row, col) order.

Constraints:

• 0 <= sr < m, 0 <= sc < n
• Heights can be any integers and are not necessarily unique.
• m, n can be up to a few thousand, so aim for a near-linear-in-grid-size solution.

Examples

Example 1

Input: ([[5,4,3],[6,1,2],[7,8,9]], (0,0))
Output: [[0, 0], [0, 1], [0, 2], [1, 1], [1, 2]]

Explanation: From (0,0)=5: right to 4 then 3; down-diagonally water reaches 1 at (1,1) via 4->1, and 2 at (1,2) via 3->2. The 6/7/8/9 block (all >= current) are never lower, so the bottom-left and corner stay dry.

Example 2

Input: ([[1,2,3],[8,9,4],[7,6,5]], (1,1))
Output: [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]

Explanation: Start at the peak 9 in the center. Every other cell is reachable by a strictly-decreasing path spiraling outward (9->8->7->...->1 and 9->4->3->2->1, etc.), so the entire grid becomes wet.

Hints

1. This is a directed flood-fill: from each cell you may only move to a strictly-lower 4-directional neighbor. Because every move strictly decreases height, you can never revisit a cell, so a single BFS or DFS from the start visits each reachable cell exactly once.
2. Equal heights block flow (the rule is strictly lower). Mark cells visited when you enqueue them to avoid duplicates, and collect every dequeued cell as wet.