🎮地牢逃生指南：论如何优雅地绕开所有小偷
你是一名勇者，代号“零”，此刻正站在一座 n × n 地牢grid的左上角 (0,0)。地牢的某些格子里藏着面目可憎的小偷（grid[r][c] = 1），他们不偷装备，专偷你辛苦攒下的金币。你的任务是从 (0,0) 走到右下角的出口 (n-1, n-1)。移动规则很传统：上下左右随便走，但不能斜着飞（地牢天花板太矮，轻功施展不开）。最关键的是：你希望整条路尽可能远离小偷。毕竟离小偷越近，你的钱包就越危险。
那么问题来了：怎么衡量一条路够不够"安全"？
一条路径的安全系数，定义为整条路径上的所有格子中，离小偷距离最小的那个值。换句话说，就是你这一路上最危险的那一格距离小偷有多远。安全系数越大，说明你这一路最危险的时候也离小偷挺远，体验舒适。
你要找的，就是所有从入口到出口的路径中，最大的安全系数到底是多少。
开胃菜：如果小偷已经堵门了？
先说个扎心的情况：如果起点 (0,0) 或终点 (n-1,n-1) 本身就是小偷老巢 (grid[r] [c]=1)，那你的冒险还没开始就结束了。安全系数注定是 0，因为你一出生就被包围了——就像刚进副本就发现BOSS站在复活点上——别挣扎了，直接返回 0 完事（除非你光脚不怕穿鞋的，但任务描述里没给你这个隐藏选项）。
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return 0
侦察阶段：多源 BFS 扫描每个格子的“安全分”
排除掉上面的倒霉情况后，你决定先做个详细的地图侦察。“知己知彼，百战不殆”，这句老话在游戏里同样适用——你不会不带地图就去开荒对吧？
于是，你掏出了大杀器——多源 BFS 探测卫星。传统 BFS 是从一个点开始扩散，像往湖里扔一颗石子；多源 BFS 是同时从所有小偷的位置开始扩散，像同时在湖里扔了一堆石子，看谁的波纹先扫到某个点。
具体操作如下：
- 初始化：把所有小偷格子同时扔进队列（像卫星同时锁定所有贼窝），它们的距离设为 0；
- 层层扩散：每次从队列里取出一个点，向四个方向扩展。第一次扫描到某个格子时，记录的距离就是它到最近小偷的曼哈顿距离；
- 完成扫描：O(n²) 时间后，你就得到了一张完整的"安全地图" dis[r] [c]，数值越大越安全，数值为 0 的地方就是小偷的老巢
这一步就像在游戏里开了全图视野，每个格子离最近的敌人有多远一目了然。
# dis[][]: 存储每个点到最近小偷的距离
dis = [[-1] * n for _ in range(n)] # -1表示未访问
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)] # 四个方向
# 初始化：所有小偷位置入队
q = deque()
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
dis[i][j] = 0
q.append((i, j))
# 多源BFS计算每个点到最近小偷的距离
while q:
x, y = q.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and dis[nx][ny] == -1:
dis[nx][ny] = dis[x][y] + 1
q.append((nx, ny))
现在你手里有了这张安全地图，接下来的问题就是：怎么用它找到那条"最安全"的路径？
找一条从左上到右下的路，让路上最小的那个数字尽量大。
解法一：二分查找
既然不知道最优的安全系数是多少，但你至少能回答一个问题：是否存在一条从入口到出口的路径，路上每个格子的安全值都 ≥ K？ 如果有，那真正的安全系数至少是 K。
显然，K 越小越容易满足，K 越大越困难，这不就是二分查找最喜欢的单调性吗？于是你直接把 K 扔进二分锅里翻炒：
每次猜一个中间值 mid，用 BFS 或 DFS 检查：只走安全值 ≥ mid 的格子，能不能从起点到终点。能，说明门槛还能再高点，lo = mid + 1（贪心本性暴露）；不能，就说明门槛太高了，hi = mid - 1（该降降期望了）。反复试探，最终夹出最大的可行门槛 k 。
方法很稳妥，就是有点磨叽——每次二分都要重新扫一遍地图，就像反复翻看同一本攻略书的铁憨憨。
# 已有 dis 安全地图
def check(limit: int) -> bool:
visit = [[False] * n for _ in range(n)]
q = deque()
q.append((0, 0))
visit[0][0] = True
while q:
x, y = q.popleft()
if x == n-1 and y == n-1:
return True
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if (0 <= nx < n and 0 <= ny < n
and not visit[nx][ny] and dis[nx][ny] >= limit):
q.append((nx, ny))
visit[nx][ny] = True
return False
# 二分查找
res = 0
lo, hi = 0, min(dis[0][0], dis[n-1][n-1])
while lo <= hi:
mid = (lo + hi) // 2
if check(mid):
res = mid
lo = mid + 1
else:
hi = mid - 1
return res
时间复杂度：O(n² log n)。多源 BFS 预处理 O(n²)，二分 log(n) 次，每次 BFS 检查又是 O(n²)。 空间复杂度：O(n²)。
解法二：潜行大师的直觉（Dijkstra 最大瓶颈路）
你合上二分的攻略，眉头一皱：每次检查都要重新 BFS，就像在迷宫里反复走已经探过的路，太死板了。能不能一次搞定？你想起江湖上的一种传说：把安全值看作“路宽”，要找一条从起点到终点“最窄处最宽”的路径。这不就是经典的最大瓶颈路径问题吗？
于是你套上 Dijkstra 的风衣(贪心 + 松弛)，化身潜行大师，只不过把"累加距离"换成"维护最小值"，把"找最短"换成"找最大最小值"。具体来说：
用一个最大堆维护当前所有探索到的路径，按该路径的瓶颈值（即整条路径上最危险那一步的安全系数）从大到小排序。起点的瓶颈值就是 dis[0][0]。每次从堆里弹出瓶颈值最大的路径，然后用它向四周扩展：走到邻居 (nx, ny) 时，新路径的瓶颈值是 min(当前瓶颈值, dis[nx][ny])（经典的木桶效应——一个短板拉低全家）。
如果这个新瓶颈值比已知的到达该格子的最优瓶颈值更大，就更新记录并入堆。因为你永远优先探索“当前最安全”的路径，所以第一次弹出终点时，那个瓶颈值就是全局最优——完全不用等所有路径都跑完。
这样，你只需在安全地图上跑一次 Dijkstra 变种，没有二分的重复扫描，复杂度还是 O(n² log n)，但实际常数更小，优雅得像在刀尖上跳舞。
# 已有 dis 安全地图
# Dijkstra算法变种：找"最大最小值"路径，就是最大化一条路径的瓶颈（路径上最危险的那一步的安全系数）
visit = [[False] * n for _ in range(n)]
visit[0][0] = True
pq = [(-dis[0][0], 0, 0)]] # 优先队列用负数技巧得到最大堆效果：每次弹出安全值最高的格子
max_safeness = min(dis[0][0], dis[n - 1][n - 1]) # 初始安全系数
while pq:
val, cx, cy = heapq.heappop(pq) # 弹出当前安全系数最高的点
val = -val # 转回正数
max_safeness = min(max_safeness, val) # 更新路径的最小安全系数
if cx == n - 1 and cy == n - 1:
break
for dx, dy in dirs:
nx, ny = cx + dx, cy + dy
if 0 <= nx < n and 0 <= ny < n and not visit[nx][ny]:
visit[nx][ny] = True
heapq.heappush(pq, (-dis[nx][ny], nx, ny))
return max_safeness
时间复杂度：O(n² log n)（堆操作）。 空间复杂度：O(n²)。
解法三：上帝视角的点灯游戏（并查集+分层优化）
前两种解法虽然都能过，但你心里总觉得差点意思。二分太磨叽，Dijkstra 虽优雅却仍要供着一座优先队列的大佛。有没有一种思路，能换个角度，彻底绕开这些麻烦？
深夜 debug 到第 42 杯咖啡时，你突然灵光炸裂：既然我想找一条路，让路上的最小安全值尽量大——那为什么不直接从最安全的格子开始，一个个"点亮"，直到起点和终点连通呢？
这就像玩一款逆向的点灯游戏：地牢里所有格子一开始都是黑的（不可用），你把它们按安全值从高到低依次点亮。每点亮一个格子，就和它四周已经被点亮的邻居连成一片（并查集合并）。当起点 (0,0) 和终点 (n-1,n-1) 第一次被连进同一片区域时——恭喜！那一刻你正在点亮的格子的距离值 d，就是你能获得的最大安全系数。
为什么？因为你按从大到小的顺序点亮格子，当前这一轮点亮的 d 就是已点亮区域里安全值最小的那一档。起点和终点刚好在这一步连通，说明恰好存在一条全程安全值 ≥ d 的路径，而 d+1 的时候它们还不连通。这不就是最优解嘛——无需二分，无需优先队列，一个排序加一个并查集就搞定了。
你兴奋地搓搓小手，准备重新跑一遍多源 BFS ，在算出每个格子到最近小偷的距离时，把所有格子塞进一个 cells 列表里，然后按距离逆序遍历（实际上BFS 天然保证了列表里的格子是按距离递增排列的，逆序就是从大到小，连 sort 都省了），再用一个带 rank 的 UnionFind 类来维护连通性——每点亮一个格子，就和四周已经被点亮的邻居合并，然后检查起点和终点是否在同一个集合里。稳如老狗。
等等。
你你盯着刚跑完的多源 BFS 发了一会儿呆，忽然醒悟：BFS 本身就是按距离一层一层扩散的啊！ 小偷在距离 0 的层，然后距离 1 的层，距离 2 的层……这分明就是天然的分组！早知如此，在 BFS 的时候顺手把同一距离的格子收集进 groups[d] 里，岂不比事后再排序聪明一百倍？
于是你立即改写 BFS，分层收集格子。等 BFS 结束，你手里不仅有一份安全地图，还多了一份从 0 到最大距离的分层花名册，直接从最大距离倒序遍历，一层一层点亮，连排序的 O(n² log n) 都省成了 O(n²)，常数小到令人发指。
既然分层已天然就绪，你索性把并查集也精简到底：什么 UnionFind 类、花里胡哨的封装统统不要。就一个 fa 数组（list 存父节点），外加一个带路径压缩的 find 函数，一行 fa[x] = find(fa[x]) 搞定一切。合并时直接 fa[find(a)] = find(b)，简单粗暴，却能在近乎 O(1) 的均摊时间内把两个格子所在的区域焊在一起。
先 BFS 分层建图，再逆序点灯 + 极简并查集判定连通，一气呵成。
def maximumSafenessFactor(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return 0
# 多源BFS，同时按距离分层
dis = [[-1] * n for _ in range(n)]
q = []
# 初始化：所有小偷位置入队
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
q.append((i, j))
dis[i][j] = 0
groups = [q] # groups[d]存储所有距离为d的点（分层记录）
while q:
tmp = q # 当前层的所有点
q = []
for i, j in tmp:
for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
if 0 <= x < n and 0 <= y < n and dis[x][y] < 0:
dis[x][y] = len(groups) # 新一层的距离
q.append((x, y))
groups.append(q) # 将当前层加入groups
# 极简并查集
fa = list(range(n * n))
def find(x: int) -> int:
if fa[x] != x:
fa[x] = find(fa[x])
return fa[x]
# 从最大距离倒序遍历，逐层点亮
for d in range(len(groups) - 2, 0, -1):
# 激活所有距离为d的点
for i, j in groups[d]:
# 与四周距离 ≥ d 的已点亮邻居合并
for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
if 0 <= x < n and 0 <= y < n and dis[x][y] >= d:
fa[find(x * n + y)] = find(i * n + j)
# 检查起点和终点是否连通
if find(0) == find(n * n - 1):
return d
return 0
时间复杂度：O(n²)，多源 BFS 分层 O(n²)，倒序点灯并查集近似 O(n²)。 空间复杂度：O(n²)。
尾声
三种解法，三种不同的快乐：二分是铁憨憨的稳妥，Dijkstra 是贪心轻功的优雅，并查集分层是逆向思维的通透。
无论你选哪条路，底层都是同一张由多源 BFS 绘制的“安全地图”。它告诉你每个格子离最近的坏蛋有多远，而你要做的，不过是在这张图上用自己的方式写一个“勇者不寄”的故事。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。