科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇围绕 codeforces-go 仓库中 LeetCode 2257 题解 展开。LeetCode 2257《统计网格中未被保卫的格子数》Count Unguarded Cells in the Grid力扣双周赛 77 第 3 题要求计算 m×n 网格中既没有警卫、也没有墙、且不被任何警卫视线覆盖的空格子数量。读完本篇你将掌握为什么逐个格子“上下左右找警卫”的暴力法是 O(mn(mn))、如何反向从警卫出发沿四个方向扫描视线把复杂度降到 O(mn)、用 -1/0/1 三种值标记格子的核心技巧以及该思路在相似题目“1222 可以攻击国王的皇后”上的推广。一、题目背景与仓库定位这道题在力扣上的题号为 2257对应仓库内文件 leetcode/biweekly/77/c/2257.md题解仓库的在线题目链接为https://leetcode-cn.com/contest/biweekly-contest-77/problems/count-unguarded-cells-in-the-grid/见 c_test.go。在仓库中力扣题解按“场次 题位”组织leetcode/biweekly/77/是第 77 场双周赛c/目录存放 C 题第三题的全部素材除题解文档外还包含c.goGo 版标准解法实现c.txt官样测试用例数据c_test.go由 copypasta/template/leetcode/generator_test.go 生成的测试入口。题解文档本身给出了 Python / Java / C / C / Go / JavaScript / Rust 七种语言的实现仓库内以 Go 为主。本文以文档为核心结合 Go 源码与测试基建逐层剖析这道“网格 视线覆盖”问题的完整解法链。二、题意与输入输出约定给定m × n的网格每个格子可能是空格、警卫或墙。函数签名Go 版见 c.gofunc countUnguarded(m int, n int, guards [][]int, walls [][]int) (ans int)m、n网格行数与列数guards警卫位置坐标列表每个元素为[x, y]walls墙位置坐标列表每个元素为[x, y]。被保卫的定义一个空格如果与某个警卫在同一行或同一列且两者之间没有任何墙则称该空格被该警卫保卫。警卫自身所在格、墙所在格都不属于“空格”也都不算作“被保卫的格子”。最终答案 网格中既非警卫又非墙、且不被任何警卫视线覆盖的空格数量。换句话说这道题的核心约束只有两个视线只能沿水平/垂直方向直线延伸上下左右四个方向墙会阻断视线墙之后的格子不再可见。从数据结构角度这是一道典型的“网格图 四个方向射线覆盖”问题仓库题解将其归类于“网格图”方向的题目单因此正确的读题顺序是先明确“空格 非警卫非墙”再明确“被保卫 被某条从警卫出发、未被墙阻断的视线扫过”。三、暴力思路及其复杂度瓶颈题解文档开篇直接给出第一个直觉依次检查每个空格子是否被保卫——即对每个空格分别向上、下、左、右四个方向逐个格子走看该方向上是否先遇到警卫说明被保卫或先遇到墙说明被阻断。该方案的伪代码形式为对每个空格 (x, y): 对每个方向 (dx, dy)上下左右: 从 (x, y) 出发沿该方向逐格移动: 若遇到警卫 → 该空格被保卫进入下一个空格 若遇到墙 → 该方向被阻断尝试下一个方向 若出界 → 尝试下一个方向复杂度分析如下空格数量为 O(mn)对每个空格最坏情况下要沿一个方向走到网格边缘单方向长度 O(m) 或 O(n)四个方向合起来每个空格最坏考察 O(mn) 个格子。因此总时间复杂度为O(mn(mn))。在m、n都较大例如 10^4 级别时这个复杂度会退化到 O(mn) 数量级的平方以上无法通过压力数据。更重要的是它重复扫描了大量格子不同空格观察同一段行/列视线时看到的墙与警卫分布完全相同逐格检查造成了大量的重复计算。这正是题解选择反向思考的根本动机。四、核心思想反向扫描视线标记而非询问题解给出的优化是反转视角不再问“这个空格是否被保卫”而是问“哪些空格会被保卫”即遍历警卫及其四个方向的视线视线所及之处的空格子标记为被保卫。这个“标记”思路与经典的“正向查询 vs 反向传播”一脉相承暴力法在查询每个空格时重复访问它的整条视线反向法从数量通常远小于空格总数的警卫出发让每个警卫“点亮”自己四个方向的视线每个空格最多被四束视线扫过天然消除了重复。核心数据结构是一张二维标记表guarded文档与源码中给出的三种取值以 Go 实现 c.go 为例取值含义0尚未被任何视线覆盖的空格也即候选答案1已被至少一个警卫视线覆盖被保卫-1障碍格子警卫所在格或墙所在格视线不得穿过技巧文档原句如果(x,y)处是警卫或者墙那么标记guarded[x][y] -1。当我们遍历到guarded[x][y] -1时就不再继续遍历。这个技巧一举三得用同一张表同时记录“障碍”与“覆盖”两类信息无需额外哈希集合视线循环的终止条件被统一为guarded[x][y] ! -1墙与警卫都会自然截断视线无需区分二者守卫自身的格子不会被误标记为“被保卫”因为它的值是-1而非1。于是整个算法分为三个阶段对应文档的叙述顺序初始化创建guarded二维数组全部为 0标记障碍把guards与walls中的格子置为-1扫描视线对每个警卫、每个方向从相邻格开始沿方向逐格移动把! -1的格子置为1直到遇到-1墙/警卫或出界为止统计遍历guarded统计值为0的格子数即为答案。五、Go 标准解法逐行解读仓库内 Go 实现位于 leetcode/biweekly/77/c/c.go与文档 2257.md 中的 Go 版代码完全一致package main // github.com/EndlessCheng/codeforces-go var dirs []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} // 左右上下 func countUnguarded(m int, n int, guards [][]int, walls [][]int) (ans int) { guarded : make([][]int8, m) for i : range guarded { guarded[i] make([]int8, n) } // 标记警卫格子、墙格子 for _, g : range guards { guarded[g[0]][g[1]] -1 } for _, w : range walls { guarded[w[0]][w[1]] -1 } // 遍历警卫 for _, g : range guards { // 遍历视线 for _, d : range dirs { // 视线所及之处被保卫 x, y : g[0]d.x, g[1]d.y for 0 x x m 0 y y n guarded[x][y] ! -1 { guarded[x][y] 1 // 被保卫 x d.x y d.y } } } // 统计没被保卫的格子数 for _, row : range guarded { for _, x : range row { if x 0 { // 没被保卫 ans } } } return }5.1 方向定义var dirs []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} // 左右上下用匿名结构体切片保存四个方向增量(0,-1)左、(0,1)右、(-1,0)上、(1,0)下。文档中 Python 版使用元组元组、Java/C/C 版使用二维数组、Rust 版使用元组数组方向定义完全一致只是语法形态不同。5.2 数组类型与内存优化guarded : make([][]int8, m) for i : range guarded { guarded[i] make([]int8, n) }guarded元素类型为int8只需容纳-1/0/1三个值一个字节足矣。相比int8 字节可将网格内存开销压缩到原来的 1/8是算法竞赛模板中常见的“按需选型”做法。Rust 版同样使用vec![vec![0i8; n]; m]C 版使用vectorint8_t各语言实现不约而同选择了最小整数类型。5.3 视线传播的边界控制for 0 x x m 0 y y n guarded[x][y] ! -1 { guarded[x][y] 1 x d.x y d.y }视线从(g[0]d.x, g[1]d.y)出发——即警卫的相邻格开始而不是警卫自己。这样避免了把-1的警卫格纳入覆盖统计也让! -1判断自然成立。循环体同时检查两个条件坐标未出界0 x x m 0 y y n当前格不是障碍guarded[x][y] ! -1。由于墙与警卫都标记为-1视线遇到二者之一都会停下guarded[x][y] 1与“继续前进”在同一轮完成被覆盖的空格即使后续再被其他方向的视线扫到也只是把1再写一遍不影响正确性。5.4 命名返回值简化统计func countUnguarded(m int, n int, guards [][]int, walls [][]int) (ans int)函数签名使用命名返回值(ans int)最终return不带表达式直接返回ans。这是 Go 惯用写法与文档中 Python 版return sum(row.count(0) for row in guarded)、Java 版return ans对应。六、七语言实现对比与关键差异题解文档给出了 7 种语言的完整代码它们在算法结构上完全同构标记 -1 → 四方向扫视线 → 统计 0差异集中在语言特性层面语言方向定义标记数组统计方式Python3元组元组DIRS (0,-1),...[[0]*n for _ in range(m)]sum(row.count(0) for row in guarded)Javaint[][] DIRSint[][] guarded new int[m][n]双重循环计数x 0Cconstexpr int DIRS[4][2]vectorint8_tranges::count(row, 0)Cstatic const int DIRS[4][2]动态calloc二维数组双重循环 末尾freeGo匿名结构体切片[][]int8双重循环累加ansJavaScriptconst DIRS [[...],...]Array.from({length:m}, ()Array(n).fill(0))双重循环Rustconst DIRS: [(i32,i32);4]vec![vec![0i8; n]; m]flatten().filter(...).count()值得注意的语言细节C 版需要手工管理内存calloc(n, sizeof(int))逐行分配并在返回前逐行free这与 Rust/Go 的 GC 或所有权管理形成鲜明对比Rust 版在边界判断上做了下标转换把i32坐标先as usize再比较x m y n利用无符号类型天然非负的特性简化了0 x这一半条件Python 版把“统计没被保卫”写成sum(row.count(0) for row in guarded)一行完成遍历计数C 版使用ranges::count(row, 0)C20 ranges 库替代手写循环。各语言视线传播的主循环逻辑完全等价从警卫相邻格出发、! -1即置 1 并前进。这也说明本题的解法核心与具体语言无关是纯算法思想层面的优化。七、复杂度分析文档末尾给出结论时间复杂度O(mn)。每个格子至多被标记 4 次。理解这个上界的关键每个格子最多可能被来自四个方向左、右、上、下的视线扫到各一次因此所有视线扫描的总工作量不超过4·mn再加上初始化的 O(mn) 与最终统计的 O(mn)整体为 O(mn)。相比暴力法 O(mn(mn))在行数与列数相近时相当于把一个因子降了下来是数量级上的改善。空间复杂度O(mn)用于guarded二维标记数组Go/C/Rust 版用int8存储实际占用m·n字节。八、仓库中的测试基建从题解到可运行验证题解仓库并非只有算法思路还配套了可直接运行的验证链路。c目录下的三个文件构成了一个完整的“题解 用例 测试”闭环8.1 测试用例文件 c.txtc.txt 存储官样测试数据按“每 5 行一组”组织4 个输入参数 1 个期望输出4 6 [[0,0],[1,1],[2,3]] [[0,1],[2,2],[1,4]] 7 3 3 [[1,1]] [[0,1],[1,0],[2,1],[1,2]] 4第一组用例含义4 行 6 列网格3 个警卫位于(0,0)、(1,1)、(2,3)3 面墙位于(0,1)、(2,2)、(1,4)期望答案是 7。第二组用例3×3 网格中心(1,1)一个警卫四周 4 面墙围住它答案为 4四个角落空格均不被保卫。第二组正是对“墙阻断视线”的针对性用例被墙围住的警卫视线完全被阻断验证了! -1终止条件的正确性。8.2 测试入口 c_test.goc_test.go 是自动生成的测试入口func Test_c(t *testing.T) { targetCaseNum : 0 // -1 if err : testutil.RunLeetCodeFuncWithFile(t, countUnguarded, c.txt, targetCaseNum); err ! nil { t.Fatal(err) } }它调用 leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithFile按函数签名的入参个数fNumIn与出参个数fNumOut把c.txt切分为用例组本题tcSize 4 1 5逐组反射调用countUnguarded并与期望输出比对。targetCaseNum 0表示跑全部用例设为-1则只跑最后一组。这套由copypasta/template/leetcode/generator_test.go生成的测试基建让仓库内数百道力扣题都能“用例文件 一行测试函数”即插即用。九、相似题目与思路推广文档在“相似题目”一节给出1222. 可以攻击国王的皇后。该题与 2257 的关联点在于**“从攻击者出发沿八个方向扫视线”**的同构思想国王相当于被保卫者棋盘上的皇后相当于警卫皇后沿八个方向比本题多四个斜向的视线只要不经过其他棋子就能“攻击”国王。两道题的解法框架一致——定义方向数组、沿方向逐格推进、遇障碍棋子/墙即停。仓库中该题对应的测试位于 leetcode/weekly/158/b/b_test.go其内嵌的 3 组测试用例直接展示了输入输出形态examples : [][]string{ { [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], [0,0], [[0,1],[1,0],[3,3]], }, // ... } if err : testutil.RunLeetCodeFuncWithExamples(t, queensAttacktheKing, examples, targetCaseNum); err ! nil { t.Fatal(err) }若沿 1222 的思路推广 2257可自然延伸出两点把本题的方向数从 4 扩到 8增加四个斜向即可覆盖“国王被八个方向攻击”的同型问题视线覆盖类问题统一适用“反向扫描 障碍终止”模板方向数组负责几何! -1负责障碍语义二者解耦后即可应对不同方向数与不同障碍规则。十、小结一份可复用的“视线覆盖”模板回顾整条解题链路识别模型空格、警卫、墙 → 三类格子用0/1/-1三值标记表统一承载选择方向四方向数组左、右、上、下是视线扫描的最小几何单元反向传播从数量少的警卫出发扫描视线避免逐空格重复查询复杂度从 O(mn(mn)) 降到 O(mn)障碍终止guarded[x][y] -1同时覆盖“墙阻断”与“不把警卫格算作被保卫”两个语义统计答案数0的个数即为未被保卫的空格数。这套“三值标记表 方向数组 视线传播”的组合在仓库题解中与 1222八方向变体互相印证是网格射线类题目的通用模板。读者可在 2257.md 查阅七语言完整实现在 c.go 与 c_test.go 中查看可直接运行的 Go 版代码与测试闭环并借助 leetcode/testutil/leetcode.go 理解仓库的用例驱动测试机制。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐JavaScript 最大子数组问题详解从 O(n²) 暴力枚举到 O(n) 线性扫描JavaScript 最大子数组问题详解从 O n² 暴力枚举到 O n 线性扫描 最大子数组Maximum Subarray是数组算法中的经典问题给定文档教程前端LeetCode 1800 最大升序子数组和Maximum Ascending Subarray Sum全解从 O(n²) 暴力到 O(n) 单遍扫描LeetCode 1800 最大升序子数组和Maximum Ascending Subarray Sum全解从 O n² 暴力到 O n 单遍扫描 本篇技示例工程教程力扣 3225 网格操作最大分数从 O(n^4) 超时到 O(n^2) 的 DP 优化全解codeforces-go 仓库实战力扣 3225 网格操作最大分数从 O n^4 超时到 O n^2 的 DP 优化全解codeforces go 仓库实战 导读 本文以 LeetCode科学计算上一篇告别云端依赖用Vosk-Browser在浏览器里打造智能语音助手下一篇如何快速找回消失的网页网页时光机浏览器插件完整使用指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考