🎮0-1网格求生指南：血条战士 01-BFS 的觉醒！
你是一个 血条战士，初始满血 health 点。你站在矩形网格的左上角 (0,0)，准备冲向右下角的传送门 (m-1,n-1)。 网格里只有两种地板：绿草地 0 和陷阱 1。踩到绿草地，毫发无伤；踩到陷阱，当场 -1 血。
规则很残酷：任何时候你的血量必须大于 0，一旦血条见底，直接原地去世。就算冲到传送门前，踏进去那一刻血量也得 >0，否则倒在终点线上也算输。
你的目标很简单：活着到达终点。
这是一场“最小受伤大赛”
你先算了笔账：不管你在网格里怎么蛇皮走位，这一路踩到的陷阱总数，就是你整趟旅程的“受伤点数”。只要存在一条路，能让你从起点到终点的受伤点数 严格小于 你的初始血量 health，你就一定能活着通关。
于是你恍然大悟——哪有什么刀山火海，策划压根就是在考你数学。所谓“最小伤害路”，翻译过来就三个字：最短路。
在这张 0-1 网格里，找一条从左上到右下的路径，使得沿途经过的 1 的个数最少。
Dijkstra（最短路）
如果你是个愣头青，从起点闷头乱冲，大概率走到一半就发现血条飙红、后路已断，只能仰天长叹：“早知道换条路了……”
痛定思痛，你用“读档重来”的神技，悟出第一招保命法门：带优先级的探索——也就是 Dijkstra 算法。从此，你不再是个无头苍蝇，而是化身为精打细算的铁公鸡旅人，永远先探最安全的方向，小心翼翼试验每一寸土地。
你准备好一个魔法小本 dist，记录到达每个格子的 当前最小受伤次数，一开始全部写成 -1（表示"从未涉足"）。起点的受伤次数直接等于 grid[0][0]——没错，起点本身也可能是个阴险的陷阱，先扣为敬。你把起点塞进一个优先队列（小顶堆），在"轻伤优先"的原则下层层推进：
每次从堆顶请出受伤最轻的格子，先核对它是否已经在小本上被"盖章定案"（dis ≥ 0）。如果是，说明这条线索是迟到的"马后炮"——已经有一条更好的路径写进本子了，果断扔掉；否则，它就是目前的最优解，立刻盖章（写入 dis），并向四个邻居探头张望。凡是还没被盖章的邻居（dis < 0），就把这个邻居和"当前受伤 + 该邻居伤害"打包丢进优先队列，让它排队等登场。
直到队列彻底清空，小本里便刻满了从起点到每个可达格子的最小受伤次数——而右下角 dis[m-1][n-1]，正是你千辛万苦要找的那条最苟路线的代价。如果它 < health，恭喜，血条足够你浪。
def findSafeWalk(grid: List[List[int]], health: int) -> bool:
m, n = len(grid), len(grid[0])
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
dis = [[-1] * n for _ in range(m)] # 魔法小本，-1 表示"从未涉足"
q = [(grid[0][0], 0, 0)] # 优先队列（小顶堆），起点先入队
while q:
val, x, y = heapq.heappop(q) # 弹出当前累积伤害最轻的格子
if dis[x][y] >= 0: # 已盖章？马后炮，扔掉
continue
dis[x][y] = val # 盖章定案，记录最优受伤次数
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and dis[nx][ny] < 0:
heapq.heappush(q, (val + grid[nx][ny], nx, ny)) # 邻居入队
return dis[-1][-1] < health
复杂度：O(mn log(mn))——最坏情况每个格子都要入堆一次，堆操作log(mn)。
双端口袋与 01BFS
跑完 Dijkstra，你盯着那个 O(mn \log(mn)) 的复杂度，觉得有点冤——这破地图只有两种伤害——踩草地不掉血（0），踩陷阱掉 1 血（1），就两个档位，干嘛还要雇个堆来排序？
杀鸡焉用牛刀。你果断扔掉优先队列，掏出一个双端队列——这玩意儿两头都能塞东西，堪称"插队神器"。核心操作只有两条：遇到草地就塞到队首，优先走；遇到陷阱就塞到队尾，等平坦的走完再说。这就是01BFS。
你走得更快了。因为你永远在“不增加受伤”的前提下疯狂扩张版图，只有万不得已才去吃陷阱。伤害只有 0 和 1 两个档位，队列里躺着的格子，受伤次数要么是 k，要么是 k+1——从队首到队尾严格单调不减，天然保持从小到大的顺序，跟 Dijkstra 一样正确，却完全不需堆排序。
def findSafeWalk(grid: List[List[int]], health: int) -> bool:
m, n = len(grid), len(grid[0])
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
dis = [[float('inf')] * n for _ in range(m)]
dis[0][0] = grid[0][0]
q = deque()
q.appendleft((0, 0))
while q:
x, y = q.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
cost = dis[x][y] +grid[nx][ny]
if cost < dis[nx][ny]:
dis[nx][ny] = cost
if grid[nx][ny] == 0:
q.appendleft((nx, ny)) # 草地插队
else:
q.append((nx, ny)) # 陷阱排队尾
return dis[-1][-1] < health
复杂度：O(mn)，每个格子只进出队列一次，双端队列每次操作 O(1)，比 Dijkstra 快了一个 log 身位。
剪枝与“终点直通车”
01-BFS 已经够快了，但你还不满足——明明有些路走到一半就已经"必死无疑"，你却还傻乎乎地继续往外扩展，这不是浪费感情吗？
剪枝思路很简单：在探索邻居时，如果从起点到该邻居的累积伤害已经 ≥ health，那这条路径注定无法让你活着通关——别入队了，直接掐断。不合法的格子连进队列的资格都没有，搜索树当场修剪干净。
光剪枝还不够。你又悟出一层更深的奥义：不管是 Dijkstra 还是 01-BFS，格子出队的顺序都是按受伤次数从小到大的。这意味着——你第一次从队列里掏出终点 (m-1, n-1) 的那一刻，手里的受伤次数就是全图最优解！
何必探完整张地图？剪枝 + 直通车双管齐下，终点一到，直接宣判：
- 如果 最小受伤次数 < health → 大喊一声 true，开传送门溜了。
- 如果 最小受伤次数 ≥ health → 苦笑一声 false，老老实实读档吧。
def findSafeWalk(grid: List[List[int]], health: int) -> bool:
m, n = len(grid), len(grid[0])
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
dis = [[float('inf')] * n for _ in range(m)]
dis[0][0] = grid[0][0]
q = deque()
q.appendleft((0, 0))
while q:
x, y = q.popleft()
if x == m - 1 and y == n - 1: # 终点到手，当场宣判
return True
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
cost = dis[x][y] + grid[nx][ny]
if cost >= health: # 入队前剪枝：必死之路，不配入队
continue
if cost < dis[nx][ny]:
dis[nx][ny] = cost
if grid[nx][ny] == 0:
q.appendleft((nx, ny))
else:
q.append((nx, ny))
return False # 队列清空仍未到达终点，无解
尾声
你到达了终点，胸口的血条摇摇欲坠，但硬是没归零。没有在半路被陷阱榨干，也没有在最后一步功亏一篑，稳得连你自己都有点意外。
一路下来，Dijkstra 是你的稳健老哥，堆排序兜底不翻车；01-BFS 是你的飙车利器，双端队列省掉过路费；剪枝 + 终点直通车是最终形态——死路不踩，到站就下，用最少的代价趟穿了整张 0-1 网格。
存档已保存，下张地图见。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。