科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文以 codeforces-go 仓库中 leetcode/season/2023spring2/c/README.md 的题解笔记为核心系统讲解力扣杯 2023 春季战队赛 T3「提取咒语」的最优解法将「位置 提取进度」编码为三重状态(i, j, k)后做 BFS 最短路搜索。读完本文你将掌握这类「网格移动 顺序收集/提取」题型的通用建模方法并看到该题在仓库内的 Go 模板、测试用例与测试框架的完整配套。一、题目背景网格中按顺序提取咒语本题出自力扣杯 2023 春季个人赛/战队赛题目「提取咒语」仓库对应位置为 leetcode/season/2023spring2/c。题面可概括为给定一个m × n的字符网格matrix每一行是一个字符串以及一个目标字符串mantra咒语初始时玩家位于左上角(0, 0)每一步可以从当前格移动到上、下、左、右相邻的四格之一也可以在当前格原地提取字符前提是当前格字符恰好等于咒语中下一个待提取字符每步花费时间均为 1要求按顺序从mantra[0]到mantra[l-1]收集齐咒语求最少步数若无法完成返回-1。仓库测试文件 c_test.go 中保留了该题在力扣上的题号kjpLFZ数据结构为func extractMantra(a []string, s string) int即传入[]string矩阵每行与咒语字符串返回最少步数。二、核心思路把「提取进度」加入状态转化为三维 BFS2.1 为什么朴素 BFS 不够若只把位置(i, j)当作状态无法区分「当前已经提取到咒语的第几个字符」——到达同一格时已经集齐的字符数不同后续所需步数完全不同。因此必须把提取进度一并纳入状态。2.2 三重状态(i, j, k)的定义继承原题解原题解给出如下状态机这是全文的灵魂状态为(i, j, k)表示当前在格子(i, j)接下来要去提取mantra[k]即前k个字符已经提取完毕0 ≤ k ≤ ll为咒语长度提取转移如果matrix[i][j] mantra[k]则无需移动即可提取该字符状态变为(i, j, k1)移动转移枚举当前格周围四个格子移动到(i, j)提取进度k不变状态变为(i, j, k)初始状态(0, 0, 0)位于起点一个字符都没提取终点k l即所有字符均已提取完毕。在这个状态空间里每一步提取或移动一格都是一条权为 1 的边因此从初始状态到任意(i, j, l)状态的最短路径长度就是答案标准 BFS 即可求解。若 BFS 结束后仍未到达k l返回-1。2.3 剪枝三维 visited 数组状态总数只有m × n × (l1)个每个状态至多入队一次。因此用vis[i][j][k]布尔数组去重即可这也是 BFS 最短路的正确性保证首次访问即最短路后到的同一状态不可能更优。三、Python 3 参考实现原题解代码原 README 中给出的 Python 实现逐层BFS 按层扩展完成上述状态机class Solution: def extractMantra(self, matrix: List[str], mantra: str) - int: m, n len(matrix), len(matrix[0]) q [(0, 0, 0)] # 起点 vis {q[0]} step 1 while q: tmp q q [] for i, j, k in tmp: if matrix[i][j] mantra[k]: # 可以提取 if k len(mantra) - 1: # 下一步就是终点直接返回 return step p (i, j, k 1) if p not in vis: vis.add(p) q.append(p) # 枚举周围四个格子 for x, y in (i 1, j), (i - 1, j), (i, j 1), (i, j - 1): if 0 x m and 0 y n: p (x, y, k) if p not in vis: vis.add(p) q.append(p) step 1 return -1 # 无法到达终点两点细节说明step从 1 开始计数代表「已经付出的行动步数」当某状态在当前位置能够提取mantra的最后一个字符时下一次行动即可到达终点k l因此直接返回当前step采用「层扩展」写法tmp q; q []天然保证同层状态同步处理无需引入距离数组也便于直接返回最小步数。四、Go 实现对齐仓库模板与测试框架仓库中的题解模板文件 c.go 目前保留了函数签名与c_test.go中调用的函数名完全一致package main // https://space.bilibili.com/206214 func extractMantra(a []string, s string) (ans int) { m, n : len(a), len(a[0]) return }按同样的状态机可以补全为如下 Go 实现与 Python 版一一对应供本地验证package main type state struct{ i, j, k int } func extractMantra(a []string, s string) int { m, n : len(a), len(a[0]) // vis[i][j][k]是否访问过状态 (i,j,k)k 最多到 len(s)终点 vis : make([][][]bool, m) for i : range vis { vis[i] make([][]bool, n) for j : range vis[i] { vis[i][j] make([]bool, len(s)1) } } q : []state{{0, 0, 0}} vis[0][0][0] true dirs : [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} step : 1 for len(q) 0 { tmp : q q nil for _, st : range tmp { if a[st.i][st.j] s[st.k] { // 可以提取 if st.k len(s)-1 { // 下一步就是终点 klen(s) return step } ns : state{st.i, st.j, st.k 1} if !vis[ns.i][ns.j][ns.k] { vis[ns.i][ns.j][ns.k] true q append(q, ns) } } // 枚举周围四个格子 for _, d : range dirs { x, y : st.id[0], st.jd[1] if 0 x x m 0 y y n { ns : state{x, y, st.k} if !vis[x][y][ns.k] { vis[x][y][ns.k] true q append(q, ns) } } } } step } return -1 // 无法到达终点 }4.1 仓库测试框架如何驱动本题c_test.go 使用仓库自带的力扣测试工具链func Test_c(t *testing.T) { targetCaseNum : 0 // -1 if err : testutil.RunLeetCodeFuncWithFile(t, extractMantra, c.txt, targetCaseNum); err ! nil { t.Fatal(err) } if err : testutil.RunFuncWithRandomInput(t, extractMantra); err ! nil { t.Fatal(err) } }其中RunLeetCodeFuncWithFile定义在 leetcode/testutil/leetcode.go它按「每入参个数 出参个数行一组」解析c.txt再通过反射调用目标函数并与期望输出比对targetCaseNum 0表示跑全部用例设为-1则只跑最后一组。测试用例文本 c.txt 内容如下[sd,ep] speed 10 [abc,daf,geg] -1第 1 组矩阵[sd,ep]2 行 2 列咒语speed期望输出10即最少 10 步第 2 组矩阵[abc,daf,geg]咒语无法集齐例如目标字符在网格中根本不存在期望输出-1。可在仓库根目录直接运行go test ./leetcode/season/2023spring2/c -run Test_c -v五、复杂度分析沿用原题解的复杂度结论时间复杂度O(mnl)其中m、n分别为matrix的行数和列数l为mantra的长度。状态总数m × n × (l1)每个状态做常数次转移提取 1 次 四方向移动 4 次空间复杂度O(mnl)主要由三维 visited 数组或 Python 版的 set 集合承载BFS 队列在最坏情况下也达到状态总数规模。当l较大时mnl可能不小但本题网格与咒语长度均在可控范围内该复杂度下 BFS 完全可过这也是「以空间换清晰建模」的典型取舍。六、扩展与可迁移的模型从本题可提炼一个通用模式在后续网格类 BFS 题中可直接复用凡是在网格移动之外还带有「顺序进度」「剩余资源」「已携带物品」等一维连续约束的就把该维度加进 BFS 状态使状态空间成为位置维度 × 进度维度的笛卡尔积再用多维 visited 剪枝。例如仓库中大量网格题见 copypasta/graph_grid.go、copypasta/search.go 等通用图与搜索工具以及 copypasta/template/leetcode 下的 LeetCode 模板都遵循「先确定状态、再讨论转移、最后验证终点」的三步法。若遇到状态空间仍过大如mnl接近极限的情形可以进一步考虑 0-1 BFS、双向 BFS 或 A* 等优化手段但在本题约束下并不必要。参考文件索引原题解笔记leetcode/season/2023spring2/c/README.mdGo 模板leetcode/season/2023spring2/c/c.go测试驱动leetcode/season/2023spring2/c/c_test.go测试数据leetcode/season/2023spring2/c/c.txt力扣测试框架leetcode/testutil/leetcode.go赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 力扣杯 2023 春·战队赛题解runeReserve 排序后相邻扫描求最长符文段codeforces go 力扣杯 2023 春·战队赛题解runeReserve 排序后相邻扫描求最长符文段 本篇题解对应 leetcode/season/科学计算力扣 2022 秋季赛个人赛 D 题三开关状态机树形 DP 关闭二叉树全部灯codeforces-go 仓库实战解析力扣 2022 秋季赛个人赛 D 题三开关状态机树形 DP 关闭二叉树全部灯codeforces go 仓库实战解析 本文基于 codeforces go科学计算力扣杯 2023 春·战队赛第四题进化记录字典序最小化递归 子树排序——codeforces-go 题解与源码解析力扣杯 2023 春·战队赛第四题进化记录字典序最小化递归 子树排序——codeforces go 题解与源码解析 本文围绕力扣杯 2023 春·战队科学计算创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考