科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇文章以 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] healthclass Solution { private static final int[][] DIRS {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; public boolean findSafeWalk(ListListInteger 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]; Dequeint[] 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(vectorvectorint grid, int health) { int m grid.size(), n grid[0].size(); vectorvectorint dis(m, vectorint(n, INT_MAX)); dis[0][0] grid[0][0]; dequepairint, 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 : id.x, jd.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 写法一脉相承。写法二提前判断尽早返回第二种写法在此基础上做了两个提前返回的优化可以省掉大量不必要的遍历扣血提前耗尽取出节点时若dis[i][j] health说明走到这里血已经扣完题目要求严格 health不可能再走通直接返回False提前抵达终点取出节点时若已经到达(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(ListListInteger 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]; Dequeint[] 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(vectorvectorint grid, int health) { int m grid.size(), n grid[0].size(); vectorvectorint dis(m, vectorint(n, INT_MAX)); dis[0][0] grid[0][0]; dequepairint, 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 : id.x, jd.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最小扣血仍不小于 33×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 时用双端队列代替最小堆这一核心思想后遇到同类题目即可直接套用本文与仓库模板的代码骨架。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 力扣双周赛 139 题解从 0-1 BFS 到前后缀分解与 LIScodeforces go 力扣双周赛 139 题解从 0 1 BFS 到前后缀分解与 LIS 力扣第 139 场双周赛共四题本仓库 leetcode/bi科学计算codeforces-go 仓库实战解析用栈一行思路解 LeetCode 双周赛 132 第 1 题 Clear Digitscodeforces go 仓库实战解析用栈一行思路解 LeetCode 双周赛 132 第 1 题 Clear Digits 本篇文章以 codeforce科学计算BFS 求无向无权图最短环LeetCode 双周赛 101 第 4 题「Shortest Cycle in a Graph」全解BFS 求无向无权图最短环LeetCode 双周赛 101 第 4 题「Shortest Cycle in a Graph」全解 本篇文章以 leetcode科学计算上一篇Czkawka 完整上手指南免费开源的重复文件、相似图片与空文件夹查找工具下一篇老Mac投影多屏输出OpenCore Legacy Patcher 完整实战教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考