企业官网建设流程全解析

• 科学计算

本篇文章以 leetcode/biweekly/139/b/README.md 讲解的 LeetCode 第 139 场双周赛 B 题"从网格图中安全走到终点"（Find a Safe Walk Through a Grid）为核心，系统梳理"扣血量最少 → 最短路 → 边权只有 0/1 → 0-1 BFS"的完整建模思路，并给出 Python、Java、C++、Go 四种语言的两种实现写法。同时结合本仓库 copypasta 模板库中的 0-1 BFS 模板与双端队列实现，深入讲解其底层原理。读完本文，你将掌握 0-1 BFS 的正确姿势，并能直接套用本仓库模板解决同类网格图/图论最短路问题。

问题建模：扣血量越少越好，就是求最短路

题目要求判断是否存在一条从左上角到右下角的路径，使得整条路径上"扣血"的总量严格小于给定的初始血量health。

• 网格中每个格子grid[i][j]非 0 即 1：走到值为0的格子不扣血，走到值为1的格子扣 1 点血；
• 起点(0,0)的血量消耗也要计入总扣血；
• 只有总扣血量< health时才算是"安全走通"。

从起点到终点的移动过程中，扣血量越少越好。因此本题的本质是：计算从起点到终点的最短路。

建模方式非常直观：

从(i,j)移动到与其相邻的格子(x,y)，视作一条从(i,j)到(x,y)的有向边，边权为grid[x][y]。

在这个建图下，dis[i][j]表示从起点到(i,j)的最小扣血量，最终只需判断dis[m-1][n-1] < health是否成立即可。

为什么用 0-1 BFS 而不是普通 Dijkstra

求最短路最通用的算法是 Dijkstra，但本题的边权只有0和1两种取值，可以使用更快的0-1 BFS解决。

0-1 BFS 本质上是对 Dijkstra 算法的优化。Dijkstra 依赖最小堆每次取出当前距离最小的节点，复杂度为O(E log V)；而 0-1 BFS 观察到：当边权只有 0 和 1 时，距离队列天然保持有序，只需把最小堆换成双端队列（deque）：

• 遇到边权为0的边，松弛后的节点加入队首；
• 遇到边权为1的边，松弛后的节点加入队尾。

这样保证队首始终是当前距离最小的节点，出队顺序与 Dijkstra 用小顶堆取最小值的顺序完全一致，从而免去堆的log开销，把复杂度降到O(V + E)（本题网格图中即O(mn)）。

该模板在本仓库中的通用版本见 copypasta/graph.go 的bfs01函数（注释中标注为"0-1 最短路 / 0-1 BFS"），其核心结构正是用两个 slice（一个当队首、一个当队尾）模拟双端队列，边权为 0 追加到队首队列、边权为 1 追加到队尾队列；网格图专用版本见 copypasta/graph_grid.go 的bfs01。双端队列的底层实现可参考 copypasta/deque.go——"用两个 slice 头对头拼在一起实现"，其注释明确写道"应用见 graph.go 中的 01 最短路"，三处代码相互印证，构成仓库内完整的 0-1 BFS 模板链。

写法一：完整 BFS 后统一比较

第一种写法朴素直观：跑完整个 0-1 BFS，求出所有格子的最小扣血dis，最后比较dis[m-1][n-1]与health。四个方向用方向数组DIRS（或dirs）表示。

class Solution: def findSafeWalk(self, grid: List[List[int]], health: int) -> bool: m, n = len(grid), len(grid[0]) dis = [[inf] * n for _ in range(m)] dis[0][0] = grid[0][0] q = deque([(0, 0)]) while q: i, j = q.popleft() for x, y in (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j): if 0 <= x < m and 0 <= y < n: cost = grid[x][y] if dis[i][j] + cost < dis[x][y]: dis[x][y] = dis[i][j] + cost if cost == 0: q.appendleft((x, y)) else: q.append((x, y)) return dis[-1][-1] < health

class Solution { private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; public boolean findSafeWalk(List<List<Integer>> grid, int health) { int m = grid.size(); int n = grid.get(0).size(); Integer[][] a = new Integer[m][]; int[][] dis = new int[m][n]; for (int i = 0; i < m; i++) { a[i] = grid.get(i).toArray(Integer[]::new); Arrays.fill(dis[i], Integer.MAX_VALUE); } dis[0][0] = a[0][0]; Deque<int[]> q = new ArrayDeque<>(); q.addFirst(new int[]{0, 0}); while (!q.isEmpty()) { int[] p = q.pollFirst(); int i = p[0]; int j = p[1]; for (int[] d : DIRS) { int x = i + d[0]; int y = j + d[1]; if (0 <= x && x < m && 0 <= y && y < n) { int cost = a[x][y]; if (dis[i][j] + cost < dis[x][y]) { dis[x][y] = dis[i][j] + cost; if (cost == 0) { q.addFirst(new int[]{x, y}); } else { q.addLast(new int[]{x, y}); } } } } } return dis[m - 1][n - 1] < health; } }

class Solution { static constexpr int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public: bool findSafeWalk(vector<vector<int>>& grid, int health) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> dis(m, vector<int>(n, INT_MAX)); dis[0][0] = grid[0][0]; deque<pair<int, int>> q; q.emplace_front(0, 0); while (!q.empty()) { auto [i, j] = q.front(); q.pop_front(); for (auto& [dx, dy] : DIRS) { int x = i + dx, y = j + dy; if (0 <= x && x < m && 0 <= y && y < n) { int cost = grid[x][y]; if (dis[i][j] + cost < dis[x][y]) { dis[x][y] = dis[i][j] + cost; cost == 0 ? q.emplace_front(x, y) : q.emplace_back(x, y); } } } } return dis[m - 1][n - 1] < health; } };

func findSafeWalk(grid [][]int, health int) bool { type pair struct{ x, y int } dirs := []pair{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} m, n := len(grid), len(grid[0]) dis := make([][]int, m) for i := range dis { dis[i] = make([]int, n) for j := range dis[i] { dis[i][j] = math.MaxInt } } dis[0][0] = grid[0][0] q := [2][]pair{{{}}} // 两个 slice 头对头来实现 deque for len(q[0]) > 0 || len(q[1]) > 0 { var p pair if len(q[0]) > 0 { p, q[0] = q[0][len(q[0])-1], q[0][:len(q[0])-1] } else { p, q[1] = q[1][0], q[1][1:] } i, j := p.x, p.y for _, d := range dirs { x, y := i+d.x, j+d.y if 0 <= x && x < m && 0 <= y && y < n { cost := grid[x][y] if dis[i][j]+cost < dis[x][y] { dis[x][y] = dis[i][j] + cost q[cost] = append(q[cost], pair{x, y}) } } } } return dis[m-1][n-1] < health }

注意 Go 写法中q := [2][]pair{{{}}}的妙处：用两个 slice 头对头拼起来充当双端队列，q[0]存"边权 0 松弛出的节点"（模拟队首），q[1]存"边权 1 松弛出的节点"（模拟队尾），q[cost] = append(q[cost], pair{x, y})一条语句就完成了"按边权选队首/队尾"的分流，与 copypasta/graph.go 中bfs01模板的ql/qr两个 slice 写法一脉相承。

写法二：提前判断，尽早返回

第二种写法在此基础上做了两个"提前返回"的优化，可以省掉大量不必要的遍历：

1. 扣血提前耗尽：取出节点时若dis[i][j] >= health，说明走到这里血已经扣完（题目要求严格< health），不可能再走通，直接返回False；
2. 提前抵达终点：取出节点时若已经到达(m-1, n-1)，说明找到了满足条件的最短路，直接返回True。

class Solution: def findSafeWalk(self, grid: List[List[int]], health: int) -> bool: m, n = len(grid), len(grid[0]) dis = [[inf] * n for _ in range(m)] dis[0][0] = grid[0][0] q = deque([(0, 0)]) while True: i, j = q.popleft() if dis[i][j] >= health: return False if i == m - 1 and j == n - 1: return True for x, y in (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j): if 0 <= x < m and 0 <= y < n: cost = grid[x][y] if dis[i][j] + cost < dis[x][y]: dis[x][y] = dis[i][j] + cost if cost == 0: q.appendleft((x, y)) else: q.append((x, y))

class Solution { private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; public boolean findSafeWalk(List<List<Integer>> grid, int health) { int m = grid.size(); int n = grid.get(0).size(); Integer[][] a = new Integer[m][]; int[][] dis = new int[m][n]; for (int i = 0; i < m; i++) { a[i] = grid.get(i).toArray(Integer[]::new); Arrays.fill(dis[i], Integer.MAX_VALUE); } dis[0][0] = a[0][0]; Deque<int[]> q = new ArrayDeque<>(); q.addFirst(new int[]{0, 0}); while (true) { int[] p = q.pollFirst(); int i = p[0]; int j = p[1]; if (dis[i][j] >= health) { return false; } if (i == m - 1 && j == n - 1) { return true; } for (int[] d : DIRS) { int x = i + d[0]; int y = j + d[1]; if (0 <= x && x < m && 0 <= y && y < n) { int cost = a[x][y]; if (dis[i][j] + cost < dis[x][y]) { dis[x][y] = dis[i][j] + cost; if (cost == 0) { q.addFirst(new int[]{x, y}); } else { q.addLast(new int[]{x, y}); } } } } } } }

class Solution { static constexpr int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public: bool findSafeWalk(vector<vector<int>>& grid, int health) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> dis(m, vector<int>(n, INT_MAX)); dis[0][0] = grid[0][0]; deque<pair<int, int>> q; q.emplace_front(0, 0); while (true) { auto [i, j] = q.front(); q.pop_front(); if (dis[i][j] >= health) { return false; } if (i == m - 1 && j == n - 1) { return true; } for (auto& [dx, dy] : DIRS) { int x = i + dx, y = j + dy; if (0 <= x && x < m && 0 <= y && y < n) { int cost = grid[x][y]; if (dis[i][j] + cost < dis[x][y]) { dis[x][y] = dis[i][j] + cost; cost == 0 ? q.emplace_front(x, y) : q.emplace_back(x, y); } } } } } };

func findSafeWalk(grid [][]int, health int) bool { type pair struct{ x, y int } dirs := []pair{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} m, n := len(grid), len(grid[0]) dis := make([][]int, m) for i := range dis { dis[i] = make([]int, n) for j := range dis[i] { dis[i][j] = math.MaxInt } } dis[0][0] = grid[0][0] q := [2][]pair{{{}}} // 两个 slice 头对头来实现 deque for { var p pair if len(q[0]) > 0 { p, q[0] = q[0][len(q[0])-1], q[0][:len(q[0])-1] } else { p, q[1] = q[1][0], q[1][1:] } i, j := p.x, p.y if dis[i][j] >= health { return false } if i == m-1 && j == n-1 { return true } for _, d := range dirs { x, y := i+d.x, j+d.y if 0 <= x && x < m && 0 <= y && y < n { cost := grid[x][y] if dis[i][j]+cost < dis[x][y] { dis[x][y] = dis[i][j] + cost q[cost] = append(q[cost], pair{x, y}) } } } } }

这里 Go 版本的for { ... }无显式退出条件，因为提前返回都收敛在循环体内（dis[i][j] >= health返回false、到达终点返回true），循环必然在队列耗尽前结束。

复杂度分析

• 时间复杂度：O(mn)，其中m和n分别为grid的行数和列数。每个点至多入队两次（一次通过 0 边、一次通过 1 边）。
• 空间复杂度：O(mn)，用于存储dis距离数组与双端队列。

相比朴素 Dijkstra 的O(E log V)，0-1 BFS 去掉了堆排序的log因子，在本题这种网格图（边数E ≈ 4mn）上达到了线性复杂度，是"边权只有 0/1"这一特殊条件下的最优求解方案。

仓库源码对照：从题解到可运行代码

本题在仓库中的完整可运行实现位于 leetcode/biweekly/139/b/b.go，其中：

• findSafeWalk对应"写法二"（提前判断扣血耗尽与抵达终点，直接在循环内返回）；
• findSafeWalk2对应"写法一"（跑完整 BFS 后统一比较dis[m-1][n-1] < health）。

两者的实现细节与文档中 Go 代码完全一致，包括[2][]pair{{{}}}的双端队列模拟技巧。针对这个"写法二"的实现，需要注意一个边界细节：dis[0][0] >= health时（例如起点的grid[0][0] == 1且health <= 1），循环第一步就会返回false，这与题目"起点扣血也计入"的语义一致。

测试入口在 leetcode/biweekly/139/b/b_test.go，它通过testutil.RunLeetCodeFuncWithFile(t, findSafeWalk, "b.txt", 0)读取 leetcode/biweekly/139/b/b.txt 中的样例数据批量验证：

• 3×5 网格、health = 1→ 期望true（存在只扣 1 点血的路径）；
• 4×5 网格、health = 3→ 期望false（最小扣血仍不小于 3）；
• 3×3 网格、health = 5→ 期望true。

这种"题解 README + 可运行源码 + 自动测试样例"三位一体的组织方式贯穿整个仓库（如 leetcode/biweekly 下的其他场次），适合作为读者自行验证与学习 0-1 BFS 的第一手材料。

模板库中的 0-1 BFS：一图看懂通用实现

如果把本题的建图抽离出来，0-1 BFS 的通用模板就是本仓库 copypasta/graph.go 中的bfs01（图版）：

// 0-1 最短路 / 0-1 BFS // ql、qr 两个 slice 头对头实现双端队列 func (*graph) bfs01(g [][]struct{ to, wt int }, st int) []int { const inf int = 1e18 dis := make([]int, len(g)) for i := range dis { dis[i] = inf } dis[st] = 0 type vd struct{ v, d int } ql, qr := []vd{{st, dis[st]}}, []vd{} for len(ql) > 0 || len(qr) > 0 { var p vd if len(ql) > 0 { ql, p = ql[:len(ql)-1], ql[len(ql)-1] } else { p, qr = qr[0], qr[1:] } v := p.v if p.d > dis[v] { continue } for _, e := range g[v] { w, wt := e.to, e.wt newD := p.d + wt if newD < dis[w] { dis[w] = newD if wt == 0 { ql = append(ql, vd{w, newD}) } else { qr = append(qr, vd{w, newD}) } } } } return dis }

对比可见，本题 Go 写法正是把该模板"搬"到网格图上：ql/qr换成q[0]/q[1]，邻接表遍历换成四方向dirs，边权wt换成grid[x][y]。此外，copypasta/graph_grid.go 也内置了网格图专用的bfs01闭包（支持自定义起点与方向，含a[x][y] != '#'这类障碍判断），而 copypasta/deque.go 则给出了通用双端队列的完整实现（pushFront/pushBack/popFront/popBack），三份模板覆盖了"通用图 → 网格图 → 队列结构"三个层次，可满足不同场景的竞赛/刷题需求。

思考题与延伸

原题解留了一道思考题：构造一个grid，使得上述算法消耗的空间尽量多。提示：算法每个点至多入队两次，距离数组dis是空间主体；让大量格子的最短路径被反复松弛（例如构造需要先向东绕远路、再向西"回流"才能得到更小扣血的迷宫结构），可以最大化入队次数与队列长度，从而把空间用到上限O(mn)量级。

从本题可以自然延伸到更多 0-1 BFS 的经典应用场景：带权为 0/1 的边权最短路、网格图中的传送门/钥匙类问题、以及"把若干操作视作边、操作代价只有 0/1"的状态图最短路。掌握"边权只有 0 和 1 时用双端队列代替最小堆"这一核心思想后，遇到同类题目即可直接套用本文与仓库模板的代码骨架。

• 科学计算