老鼠避猫路径：最大化路径最小曼哈顿距离

题目重点：只走陆地，猫静止，路径每点安全值是到猫的曼哈顿距离。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

grid中0陆地、1水域，四方向；start/end在陆地，否则返回None。
猫坐标固定；距离是几何Manhattan，水域不会增加距离。不是猫实际追逐、不是避开半径后的最短路。

解题路线

每点安全s(v)=|r−rcat|+|c−ccat|。路径分数取min s，目标取max路径分数，属于widest path。
best[v]保存已知最大瓶颈，松弛candidate=min(best[u],s(v))，以最大best出堆。非增扩展保证第一次最终弹出目的地即为最优瓶颈。
也可二分安全阈值d，BFS只走s≥d的陆地；阈值越大可走点越少。不连通需独立返回None，不能与安全值0混淆。

手动走一遍

3×3全陆地，猫(0,0)，S(2,0)、T(0,2)：走底边、右边最小距离2，比穿中心靠猫更安全。若起点就在猫格，所有路径瓶颈≤0；有通路仍返回0而不是None。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from heapq import heappush,heappop


def safest_path(grid,start,end,cat):
    rows,cols = len(grid),len(grid[0]) if grid else 0
    if any(len(row)!=cols for row in grid):
        raise ValueError("ragged grid")
    def land(r,c):return 0<=r<rows and 0<=c<cols and grid[r][c]==0
    if not land(*start) or not land(*end):
        return None
    def safety(r,c):return abs(r-cat[0])+abs(c-cat[1])
    best={start:safety(*start)}
    heap=[(-best[start],start)]
    while heap:
        neg,u=heappop(heap);value=-neg
        if best[u]!=value:
            continue
        if u==end:
            return value
        r,c=u
        for v in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
            if land(*v):
                score=min(value,safety(*v))
                if v not in best or score>best[v]:
                    best[v]=score;heappush(heap,(-score,v))
    return None

复杂度

V=RC、E≤4V，最大堆基线O(VlogV)时间、O(V)空间；Manhattan每格O(1)，不需多源BFS。大整数坐标算术位成本另计。

易错点与追问

容易失分的边界

若题目改成猫沿陆地追赶距离，Manhattan就不代表实际最短路，需要另一距离模型。
把路径安全值相加会偏好绕路，完全改变目标。

继续深挖

猫有多个固定位置，如何用多源距离图生成每点安全？
同一grid大量S/T查询怎样用最大生成树回答瓶颈？