题目重点：两个搜索集合求交并取最高，供水与汇流是相反方向模型。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 四邻接，流动严格高→低；允许零步，所以各起点包含自己。
- 训练默认求A/B向下均可到的汇流点最高海拔；若well必须向两村供水，则从A/B逆边向上搜索。cost追问未给代价目标，留待核。
解题路线
- 构建隐式有向边，默认从A/B分别搜索可达格。交集内取最高海拔并稳定坐标tie。
- 若问供水井，井应能到A与B，等价在反图从A/B搜索。仅说“都BFS”还不足，必须定义比较邻居海拔的方向。
- 可达性与最高目标独立：DFS/BFS都能求集合，BFS层数不是最高海拔。新增cost可能要求路径和、联合费用或最大瓶颈，不能无定义自动换成Dijkstra。
手动走一遍
单行[9,8,7]，A在9、B在8：默认共同下游最高为8；上游供水版本共同最高为9。相邻等高默认没有流边；若实际允许平流，要改为≤并用visited防环。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def highest_common(grid,a,b,upstream=False):
rows=len(grid);cols=len(grid[0]) if grid else 0
if any(len(row)!=cols for row in grid):raise ValueError("ragged grid")
def reachable(start):
if not 0<=start[0]<rows or not 0<=start[1]<cols:raise ValueError("invalid start")
seen={start};todo=[start]
for r,c in todo:
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 seen:
permitted=grid[nr][nc]>grid[r][c] if upstream else grid[nr][nc]<grid[r][c]
if permitted:seen.add((nr,nc));todo.append((nr,nc))
return seen
common=reachable(a)&reachable(b)
return min(common,key=lambda v:(-grid[v[0]][v[1]],v)) if common else None
复杂度
O(RC)时间/O(RC)空间，两搜索及交集扫描。若有具体非负权最短路才讨论Dijkstra成本。
易错点与追问
容易失分的边界
- 用无向连通会忽略海拔方向。
- 把最大可达点误用优先队列而不解决双起点交集。
继续深挖
- 若要求两个村到井的合计运输成本最小，三组距离公式何时适用？
- 多个村庄共同可达时计数集合与复杂度如何增长？
