题目重点：按有向可达性遍历低处邻格，区分单起点扩散与两海洋逆向搜索。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练合同四邻接、严格更低可通行，起点也湿；若相等高度可流，改≤且仍保留visited。
- 仅求可达湿点，不模拟水量、速度、积水抬升或多个时间步。输入为非空矩形。
解题路线
- 将每个格子看节点，指向高度严格更低的邻格。从给定起点BFS/DFS，首次发现时放visited，最终集合就是所有有向可达节点。
- 正确性两方向：每个加入点由已湿点合法边到达，故有实际下降路径；对任意下降路径按长度归纳，前驱会出队检查后继，所有可达点都会被发现。
- 不要只选最低邻格；题目问所有可能变湿点，水可分支，所有低邻格都应遍历。strictly lower使图无环，但visited仍防不同路线重复处理同点。
- 作者拿LC417类比只是训练线索。两海洋题从边界反向沿高处找汇流集合；本题只有给定水源并沿低处前向探索，起点和方向都不同。
手动走一遍
训练地图[[5,4,6],[4,3,2]]从(0,0)出发，除(0,2)外都可湿；等高4邻接政策改变其他样例，不应暗中放宽。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def wet_points(heights, start):
"""Four-neighbor movement, strictly downhill; includes starting cell."""
if not heights or not heights[0] or any(len(row) != len(heights[0]) for row in heights):
raise ValueError("expected nonempty rectangular grid")
rows, cols = len(heights), len(heights[0])
r,c = start
if not (0 <= r < rows and 0 <= c < cols):
raise ValueError("start out of bounds")
wet = {start}
queue = deque([start])
while queue:
r,c = queue.popleft()
for nr,nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
if (0 <= nr < rows and 0 <= nc < cols and (nr,nc) not in wet
and heights[nr][nc] < heights[r][c]):
wet.add((nr,nc))
queue.append((nr,nc))
return wet
复杂度
O(RC)时间与空间，每格检查最多4条边；只访问k个湿点时遍历O(k)，矩形形状校验O(R)。
易错点与追问
容易失分的边界
- 把本题直接换成双海洋交集。
- 只沿一个最低点走。
- 把可达当物理水量分布。
继续深挖
- 允许平坡怎样改？
- 若允许对角邻格？
- 多水源和所有能到某汇点怎样做？
