这道题我第一次看到的时候题面其实没写完停在正方形草地位于直角坐标系中就断了。但就这半句话已经足够让我判断出它属于哪一类问题大坐标、稀疏障碍、求连通区域面积。这类题在区域赛和各类在线评测里反复出现套路非常固定可变的部分只有障碍长什么样和怎么走。下面我按自己解题和给队友讲题的顺序把这道懒羊羊吃青草完整拆一遍从题意还原到代码实现再到踩过的坑。1. 题意还原与建模先把草原变成一张图拿到一个不完整的题面第一步不是急着写代码而是把自然语言描述翻译成机器能处理的结构。这道题的场景很具体一只很能吃的羊一块巨大的正方形草地若干已经布好的陷阱问它能吃到多少草。翻译成算法语言就是在一个带障碍的区域内求从起点出发的可达区域大小。1.1 正方形草地的三种给法与互相转换正方形在直角坐标系里的给法常见的有三种我按出现频率排一下给左下角和边长、给四个顶点、给中心点和边长。这三种形式在代码里的处理差别不大核心都是先算出minx, miny, maxx, maxy四个值让整个问题回到轴对齐矩形这个最舒服的形态。如果给的是左下角(x0, y0)和边长L那四个边界直接就是x0、x0L、y0、y0L。我习惯把右边界和上边界记成开区间也就是格子只取到x0L-1这样后面算宽度的时候不用到处1少一半的差一错误。如果给的是四个顶点必须先验证它们真的是轴对齐的正方形判断方式很朴素所有点的 x 只有两种取值y 也只有两种取值并且 x 的跨度等于 y 的跨度。这一步不验证后面坑会埋得很深——万一给的是旋转 45 度的正方形那整个按列切分的思路直接作废得换成旋转坐标系或者几何方法。提醒一句如果题目的正方形是斜着放的坐标压缩那一套就不适用了。判断方法很简单看顶点坐标是不是只有两个不同的 x 值。我给一个小的转换片段把四顶点形式统一成左下角加边长long long minx min({px[0], px[1], px[2], px[3]}); long long maxx max({px[0], px[1], px[2], px[3]}); long long miny min({py[0], py[1], py[2], py[3]}); long long maxy max({py[0], py[1], py[2], py[3]}); // 这里必须断言 maxx - minx maxy - miny long long L maxx - minx;统一之后草地就是列号从x0到x0L-1、行号从y0到y0L-1的一张方格纸每个格子面积为单位 1。这一步做完后面所有的推导都只跟数字打交道跟羊和狼没关系了。1.2 陷阱到底是一个点、一个格子还是一堵墙这是这类题最容易产生歧义的地方也是题面写一半时最需要我自己拍板的地方。在连续平面上一个数学意义上的点是挡不住任何东西的羊可以从旁边绕过去绕着走能到达整个正方形答案就是L*L那这题就没意义了。所以陷阱只能理解为占据一个单位方格的实心块或者半径为 r 的圆形禁区。我按最常见、也最容易实现的那一种来建模陷阱(xi, yi)占据列xi、行yi的那个单位方格羊不能进入这个格子。这样问题就变成了标准的网格连通性问题四联通、八联通都可以按题目要求切换。如果你的原始题目里给的是陷阱的影响半径r那建模方式要换一下障碍不再是格子而是以陷阱为圆心、半径r的圆。这时候能不能穿过两个陷阱之间就变成了判断两圆之间有没有缝隙答案依赖dist(p1, p2) 2r这样的条件。这已经偏向计算几何跟坐标压缩是两个方向。我在第 7 节会简单提一下这种变体怎么处理。建模假设一定要在解题开头写清楚。我见过太多人代码写完了才发现自己对陷阱的理解跟出题人不一样白写两小时。1.3 懒羊羊的移动规则决定了算法内核能吃到的草这句话背后其实藏着两个必须明确的东西羊怎么走以及草怎么算。走法上最常见的是四联通上下左右也有题目要求八联通含对角线还有一类是只能沿直线走到底遇到陷阱或边界才转向。前两种是标准的 BFS/DFS 连通块问题第三种就变成了图形学里的光线投射或者可视图问题复杂度完全不是一个量级。草的计量上如果草地是离散格子答案就是可达格子数如果草地是连续的那还得考虑羊的嘴巴宽度、吃草半径之类。按题面巨大的正方形草地这个措辞我倾向于离散格子模型因为连续模型下巨大这个形容词没有意义。所以整道题的核心就一句话在一张L × L的网格上去掉若干障碍格求起点所在连通块的大小。如果L只有一两千到这里就可以直接开写了。麻烦的是巨大这两个字。2. 为什么直接 BFS 会炸先算清楚规模再动手我在带新人的时候发现一个普遍现象看到网格 连通块手比脑子快queue一写vis数组一开提交然后 TLE 或者 MLE。问题出在没有先算规模。这道题里的L是巨大那到底多大2.1 朴素做法的复杂度账本朴素 BFS 的时间是O(L²)空间也是O(L²)。如果L 10³那是一百万个格子随便写都能过如果L 10⁵那是一百亿个格子内存直接爆到几十 GB跑一天也跑不完如果L 10⁹——这在这类题里非常常见因为出题人喜欢用10⁹来表示坐标范围——那就是10¹⁸个格子连想都不用想。关键的地方在于陷阱的数量n通常很小比如n ≤ 1000甚至n ≤ 100。一整片草原上就挖了几百个坑绝大部分区域是干净的、同质的可我们的算法却要为每一个格子单独开一个vis标记这就是典型的计算量和信息量严重不匹配。我一般用这样一个类比跟队友解释你要统计一张巨大的白纸上被几个墨点分割成了几块区域正确做法是盯着墨点看而不是拿放大镜一格一格扫。墨点只有几百个但纸有几亿个像素扫完纸早就天亮了。2.2 稀疏性到底省在哪把10⁹ × 10⁹的网格摊开看它的结构复杂度其实完全由陷阱决定。没有陷阱的时候整块草地就是一个连通块答案是L²一行代码搞定。有陷阱的时候陷阱把整块草地切成若干块而切法只跟陷阱之间的相对位置有关。具体一点说考虑所有陷阱的 x 坐标它们把[x0, x0L)这个区间切成了若干段。任意一段内部所有列的行为是完全一样的——要么全都是空的因为这一段里没有陷阱的 x 坐标要么全都是障碍列如果这一段就是某个陷阱的 x 坐标本身。既然行为一样就没必要一列一列地区分合并成一列块就行。y 方向同理。两个方向都合并之后原本10⁹ × 10⁹的网格就变成了(3n2) × (3n2)的压缩网格。n 1000的时候是3002 × 3002约九百万个节点BFS 跑起来毫无压力。这就是坐标压缩的全部思想一句话能说完但细节上有不少讲究。2.3 一个具体数字对比我列个表把朴素做法和压缩做法的差距摊开看这个表我经常直接贴在解题报告里方案时间空间L10⁹, n1000 时可行性朴素网格 BFSO(L²)O(L²)完全不可行逐行扫描线O(n² log n)O(n)可行但实现复杂坐标压缩 BFSO(n² log n)O(n²)直接可写约 9M 节点坐标压缩 并查集O(n² α)O(n²)也可行省一点常数从表里能看出来坐标压缩是性价比最高的选择实现难度中等代码量可控正确性容易论证调试的时候还能把压缩后的网格打印出来肉眼检查。这也是我推荐新手优先掌握这个套路的原因。3. 坐标压缩把十亿的网格折叠成三千坐标压缩coordinate compression这个词在算法竞赛里出现频率极高但很多人只会背模板不知道为什么要这么写。我把它的推导过程完整走一遍理解了之后参数怎么选、边界怎么处理都是自然推出来的。3.1 区间等价类哪些列可以合并先把问题形式化。设草地覆盖的列号集合是[x0, x0L)左闭右开共L列行号集合是[y0, y0L)。定义两个列a和b是等价的如果对任意一行y格子(a, y)和(b, y)的可通行状态完全相同。由于障碍只出现在陷阱所在的列且只在该列的一个具体行上所以判断等价只需要看这一列上有没有陷阱没有陷阱的列整列都是空的跟其他空列等价有陷阱的列只有陷阱那一行是障碍跟其他列不等价。于是所有列被分成两类一类是陷阱所在的列一共最多n个另一类是没有陷阱的列但它们在空间上被陷阱列切成若干段每段内部彼此等价。行方向完全对称。这就给出了压缩规则把每一段连续的等价列合并成一个超级列宽度等于这段的列数行方向同理。压缩后的每个节点是一个矩形块面积就是宽度乘高度。3.2 关键点怎么选才不出漏合并的关键是找出分界点也就是那些必须单独成段的坐标。我的做法是对每个陷阱(x, y)往关键点集合里塞三个 x 值——x-1、x、x1y 方向同理。再加上草地本身的左右边界x0和x0L。为什么是三个而不是一个这里说三个理由每一个都对应一类容易出的错。第一个理由x本身必须加否则陷阱所在的列会被并进一个宽块里障碍就丢了。第二个理由x1必须加否则陷阱那一列会和右边一大片空列合并导致压缩后的陷阱格子宽度大于 1画出来的墙变厚了面积就算多了。加了x1之后陷阱格子一定是[x, x1)这样宽度恰好为 1 的格子跟原网格一一对应。第三个理由x-1严格来说不是必需的加不加不改变连通性结论。但我还是习惯加上因为它能让陷阱左侧那一列也独立出来调试的时候打印压缩网格人眼能跟原坐标直接对齐省掉很多脑补。另外如果题目后面追加陷阱有半径 1 的影响范围这种条件x-1就是必需的了。伪代码长这样vectorlong long xs, ys; xs.push_back(x0); xs.push_back(x0 L); ys.push_back(y0); ys.push_back(y0 L); for (auto [x, y] : traps) { if (x x0 || x x0 L || y y0 || y y0 L) continue; // 草地外的陷阱直接忽略 add(xs, x - 1, x0, x0 L); add(xs, x, x0, x0 L); add(xs, x 1, x0, x0 L); // y 方向同理 }注意add里的范围裁剪加进去的坐标必须在[x0, x0L]之内因为压缩网格只在草地范围内有意义。如果不裁边界外的坐标会凭空多出一段区间最后 BFS 会跑到草地外面去答案偏大。3.3 面积权重为什么不能只数格子压缩之后每个压缩格子代表原网格中的一片矩形区域面积是(xs[i1] - xs[i]) * (ys[j1] - ys[j])。BFS 访问到一个压缩格子时累加的是这个乘积而不是1。这一步是新手最容易写错的地方。我见过有人把压缩格子当普通格子每个格子加 1最后答案永远等于压缩网格的节点数跟真实面积差了几万倍。也见过有人只乘宽度不乘高度结果答案是一条斜线上的面积。用生活化的说法解释原来的网格是每个像素点大小一样的照片压缩之后变成了每块色块大小不一样的马赛克。你数色块个数没用得把每块色块的面积加起来。压缩的意义就在于同一块色块内部颜色一致要么全空要么全是障碍所以只需要判断一次。3.4 正确性说明压缩前后连通性真的等价吗这是必须要论证的一步不然写出来的代码自己心里都没底。命题在原网格中两个格子(a, b)和(c, d)四联通当且仅当它们所在的压缩格子(ia, jb)和(ic, jd)在压缩网格中四联通。充分性设压缩格子I和J相邻比如J在I右边。那么I的最右一列xs[i1]-1和J的最左一列xs[i1]在原网格中是相邻的两列。由于I和J都不是障碍格子这两列上对应的格子都可通行所以原网格中这两个格子相邻。这就说明压缩网格中的每条边在原网格中都能找到对应的边。必要性设原网格中(a, b)和(a1, b)相邻。如果它们属于同一个压缩格子那没什么好说的。否则a和a1之间必然存在一个关键点也就是a1是某个关键点那么(a, b)所在的压缩格子I和(a1, b)所在的压缩格子J满足xs[i1] a1即J是I的右邻居。所以压缩网格中也相邻。两个方向都成立连通性等价。这里有一个隐含条件必须满足压缩格子内部不能包含障碍。而我们的关键点选取保证了陷阱的 x 坐标一定是某个关键点所以陷阱所在的那一列一定是压缩格子的左边界任何包含陷阱的压缩格子宽度必然为 1内部不会再有第二条陷阱列。这个性质是整个论证的地基关键点选错地基就塌了。我调试这类题时有个固定动作把压缩后的网格打印成字符画障碍画#空地画.然后跟原网格的小样例逐格对照。这一步能抓出九成的错误。4. 动手实现离散化加 BFS 求连通块面积前面都是推导这一节进入代码。我把完整流程拆成四步读入与过滤、关键点收集与索引构建、障碍标记与起点定位、BFS 与面积累加。每一步都附上为什么要这么写。4.1 输入解析与陷阱过滤题面没给输入格式我按这类题的惯例定一个第一行x0 y0 L第二行n接下来n行每行一个陷阱坐标最后一行是起点sx sy。如果你的题目是给四个顶点的先按 1.1 节的方式转换一下。读入的时候要做两件事。第一件把草地范围外的陷阱丢掉。题目里经常出现灰太狼在草原上布陷阱严格说陷阱应该在草地内但输入数据里混进几个草地外的坐标是常事不做过滤的话关键点会跑到边界外压缩网格的结构就乱了。第二件重复的陷阱要去重。同一个格子放两个陷阱没有意义但不去重的话关键点会重复虽然unique之后不影响正确性但会让关键点数量虚高白白增加开销。long long X1 x0 L, Y1 y0 L; setpairlong long, long long trapSet; for (int i 0; i n; i) { long long x, y; cin x y; if (x x0 || x X1 || y y0 || y Y1) continue; trapSet.insert({x, y}); // 同时把 x-1, x, x1 和 y-1, y, y1 加入关键点 }用set存陷阱有个额外好处后面标记障碍时可以用O(log n)查询不过我们其实用不到查询因为陷阱坐标本身就保证是压缩网格某个格子的左下角直接lower_bound定位就行。4.2 关键点排序去重与索引映射关键点收集完之后必须排序去重。排序是为了让相邻两点构成一个区间去重是因为x-1、x、x1可能跟别的陷阱的关键点重合。sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); int W (int)xs.size() - 1; int H (int)ys.size() - 1;这里W和H是压缩网格的列数和行数。因为xs存的是边界点m个边界点围出m-1个区间所以要减 1。这一步减 1 忘了就是数组越界是仅次于差一错误的第二高频 bug。索引映射我建议用lower_bound现算不要提前开大数组存。原因很简单坐标是long long范围到10⁹甚至更大开数组存映射根本开不下。lower_bound每次O(log n)总调用次数是O(n)级别只有n个陷阱需要定位完全不影响复杂度。4.3 障碍标记与起点定位障碍标记很直接遍历陷阱集合用lower_bound找到它在xs和ys中的索引把压缩网格对应位置标成障碍。vectorvectorchar blocked(W, vectorchar(H, 0)); for (auto p : trapSet) { int i lower_bound(xs.begin(), xs.end(), p.first) - xs.begin(); int j lower_bound(ys.begin(), ys.end(), p.second) - ys.begin(); blocked[i][j] 1; }用char而不是bool是有讲究的。vectorbool是位压缩存储不能取地址很多场景下会出问题vectorchar每个元素 1 字节内存占用一样都是 1 bit 的逻辑对比 8 bit 的物理但访问速度更快也不会有各种诡异的编译问题。九百万个节点两个vectorchar也就 18 MB完全可以接受。起点定位稍微绕一点。起点坐标不一定恰好是关键点所以要用upper_bound找第一个大于起点的关键点再减 1 得到最后一个小于等于起点的关键点这就是起点所在的压缩列。int si (int)(upper_bound(xs.begin(), xs.end(), sx) - xs.begin()) - 1; int sj (int)(upper_bound(ys.begin(), ys.end(), sy) - ys.begin()) - 1;这里为什么不能用lower_bound举个例子xs [0, 5, 6, 10]起点sx 5。用lower_bound返回索引 1指向 5减 1 之后是 0那就跑到[0,5)这个区间去了错了。用upper_bound返回索引 2指向 6减 1 之后是 1正好对应[5,6)这个区间正确。这个坑我在比赛里踩过一次当时样例全过提交 WA 在第 7 个点查了四十分钟才发现是lower_bound和upper_bound搞反了。教训就是凡是找某个值所在的区间一律用upper_bound减一。定位完之后还要做三重检查起点是否在草地范围内、压缩索引是否越界、起点所在格子是不是障碍。三个检查缺一不可任何一个出问题都应该直接输出 0。4.4 BFS 主循环与面积累加BFS 本身没什么好讲的标准写法四个方向扩展。唯一需要注意的是面积累加的位置——在出队时累加而不是入队时。这样写的好处是每个节点只加一次不会因为重复入队而重复计算。当然如果入队时就标记vis效果是一样的。long long ans 0; queuepairint, int q; vis[si][sj] 1; q.push({si, sj}); const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1}; while (!q.empty()) { auto [i, j] q.front(); q.pop(); ans (xs[i 1] - xs[i]) * (ys[j 1] - ys[j]); for (int d 0; d 4; d) { int ni i dx[d], nj j dy[d]; if (ni 0 || ni W || nj 0 || nj H) continue; if (vis[ni][nj] || blocked[ni][nj]) continue; vis[ni][nj] 1; q.push({ni, nj}); } }ans必须用long long。面积最大可能到L²L 10⁹时是10¹⁸刚好在long long范围内9.2 × 10¹⁸但用int直接溢出成负数。这种溢出在本地小样例上永远测不出来只有大数据才会暴露所以从一开始就用long long别心疼那点内存。4.5 完整代码把所有部分拼起来就是可以直接提交的版本#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long x0, y0, L; if (!(cin x0 y0 L)) return 0; int n; cin n; long long X1 x0 L, Y1 y0 L; vectorlong long xs, ys; xs.push_back(x0); xs.push_back(X1); ys.push_back(y0); ys.push_back(Y1); auto addX [](long long v) { if (v x0 v X1) xs.push_back(v); }; auto addY [](long long v) { if (v y0 v Y1) ys.push_back(v); }; setpairlong long, long long trapSet; for (int i 0; i n; i) { long long x, y; cin x y; if (x x0 || x X1 || y y0 || y Y1) continue; trapSet.insert({x, y}); addX(x - 1); addX(x); addX(x 1); addY(y - 1); addY(y); addY(y 1); } long long sx, sy; cin sx sy; sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); int W (int)xs.size() - 1; int H (int)ys.size() - 1; vectorvectorchar blocked(W, vectorchar(H, 0)); for (auto p : trapSet) { int i (int)(lower_bound(xs.begin(), xs.end(), p.first) - xs.begin()); int j (int)(lower_bound(ys.begin(), ys.end(), p.second) - ys.begin()); blocked[i][j] 1; } if (sx x0 || sx X1 || sy y0 || sy Y1) { cout 0 \n; return 0; } int si (int)(upper_bound(xs.begin(), xs.end(), sx) - xs.begin()) - 1; int sj (int)(upper_bound(ys.begin(), ys.end(), sy) - ys.begin()) - 1; if (si 0 || si W || sj 0 || sj H || blocked[si][sj]) { cout 0 \n; return 0; } vectorvectorchar vis(W, vectorchar(H, 0)); queuepairint, int q; vis[si][sj] 1; q.push({si, sj}); long long ans 0; const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1}; while (!q.empty()) { auto [i, j] q.front(); q.pop(); ans (xs[i 1] - xs[i]) * (ys[j 1] - ys[j]); for (int d 0; d 4; d) { int ni i dx[d], nj j dy[d]; if (ni 0 || ni W || nj 0 || nj H) continue; if (vis[ni][nj] || blocked[ni][nj]) continue; vis[ni][nj] 1; q.push({ni, nj}); } } cout ans \n; return 0; }代码不长六十多行但每一行都有它存在的理由。我建议你自己手敲一遍别复制敲的过程中会自然去思考每一句为什么这么写比读十遍都管用。4.6 几类必须单独验证的边界情况写完代码先别提交拿下面这几组数据挨个跑一遍能提前抓掉大部分低级错误。场景输入特征期望行为没有陷阱n 0直接输出 L²不走 BFS 也对陷阱在草地外坐标超出范围过滤掉答案不受影响起点正好在陷阱上起点坐标与陷阱重合输出 0草地只有一格L 1压缩网格 1×1正确陷阱贴着边界x x0 或 x x0L-1关键点裁剪正确不越界陷阱把草地切成两半一排陷阱横贯只能吃到起点那一半起点在角落四角之一索引定位不越界陷阱重复给出同一坐标多次set 去重答案不变其中陷阱贴着边界和陷阱把草地切成两半这两个最值得反复测因为它们同时考验关键点裁剪和连通性判断出错的概率最高。5. 复杂度、内存与调优算法能跑对是一回事跑得快是另一回事。这一节把复杂度和资源占用量化一下方便你判断自己的实现在什么规模下是安全的。5.1 时间复杂度的完整推导整个过程分四步每步的复杂度单独看关键点收集是O(n)排序去重是O(n log n)因为关键点数量最多3n2障碍标记是n次lower_boundO(n log n)BFS 最多访问W × H个节点每个节点检查 4 条边O(n²)。总复杂度是O(n²)排序那一项被 BFS 的O(n²)吞掉了。n 1000时是9 × 10⁶次操作现代处理器一秒能做10⁸到10⁹次简单运算绰绰有余。n 5000时是2.25 × 10⁸就有点紧张了得看评测机性能。如果题目把n开到10⁵那O(n²)就彻底没戏了得换思路——通常是扫描线加并查集或者对陷阱做虚拟图上的 BFS只保留陷阱周围的O(n)个关键节点复杂度和陷阱之间的相邻关系有关。这类题会额外给出陷阱之间距离不小于某个值的约束正是为了让虚拟图的边数是O(n)的。5.2 内存占用的实际估算压缩网格的节点数是W × H最坏(3n2)²。n 1000时3002² ≈ 9 × 10⁶个节点。blocked和vis各占9 × 10⁶字节合计18 MB。队列最坏存9 × 10⁶个pairint,int每个 8 字节72 MB。加起来接近 100 MB如果内存限制是 64 MB 就悬了。几个优化方向按收益排序使用vectorint或一维数组代替vectorvectorchar减少嵌套容器的指针开销同时让内存连续缓存命中率更高。把队列换成手写的循环数组或者用vector当队列加两个指针省掉std::queue的deque开销。如果连通块不大可以在 BFS 结束后立刻swap释放vis不过这对峰值内存没帮助。我的经验是n ≤ 1000时不用优化直接写最清晰的版本n ≥ 3000时改成手写队列加一维数组再大就说明该换算法了优化常数救不了复杂度。5.3 几个能省时间的实现细节第一个是关闭同步流ios::sync_with_stdio(false); cin.tie(nullptr);输入量大的时候能省下可观的 I/O 时间。这个不是玄学实测差个两三倍很正常。第二个是用 BFS 而不是 DFS。DFS 在九百万节点的图上递归栈深可能达到百万级必然爆栈就算改成手写栈访问顺序也更不友好缓存命中率低。第三个是把blocked和vis合并成一个状态数组用 0 表示未访问、1 表示已访问、2 表示障碍这样只需要一次内存访问就能判断两种条件。这个优化在小数据上没感觉大数据上能省 10%~20% 的时间。6. 踩坑实录与排查清单这一节是我觉得整篇文章最有价值的部分。前面讲的都是正确的做法长什么样这一节讲我实际写错的时候错在哪。这些东西在学习资料里基本不会写只有真正提交过、WA 过、对拍过才会积累下来。6.1 常见错误速查表我把这些年在这类题上踩过的坑整理成表按出现频率排序你可以对照自己的代码逐条排查错误现象根因定位方式答案恒为 1 或很小面积累加忘了乘宽度/高度打印每步累加值答案接近 L² 但偏大陷阱没过滤跑到了草地外打印关键点数组段错误压缩网格索引越界少减 1检查 W、H 定义起点明明在空地上却输出 0lower_bound用错改upper_bound减 1小数据全过大数据 WAans用int溢出全部改long long障碍墙挡不住羊关键点漏了x1打印压缩网格比对多组数据后答案错乱全局数组没清空改成局部变量只有某个角落错边界坐标没裁剪检查addX范围判断表里前四条几乎覆盖了九成的错误。我特别说一下第二条答案偏大——这个坑很隐蔽因为如果所有陷阱都在草地内代码不会出问题只有题目数据里混了草地外的陷阱才会暴露。出题人有时是故意的用来区分有没有认真读数据范围。6.2 对拍最可靠的验证方式再自信的代码也要对拍。做法很简单写一个暴力版本用L ≤ 8的小网格直接BFS然后随机生成几千组数据跟压缩版对答案。暴力版的核心就是把草地老老实实展开成二维数组// 暴力版核心仅用于对拍 bool blocked[20][20]; bool vis[20][20]; int bfs(int sx, int sy, int L) { queuepairint, int q; vis[sx][sy] true; q.push({sx, sy}); int cnt 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); cnt; for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 0 || nx L || ny 0 || ny L) continue; if (vis[nx][ny] || blocked[nx][ny]) continue; vis[nx][ny] true; q.push({nx, ny}); } } return cnt; }对拍数据生成器要注意几个要点L取1到8陷阱数量0到L²陷阱坐标允许重复、允许超出范围测试过滤逻辑起点随机。这样几千组跑下来能覆盖绝大多数边界组合。我用这套方法 
长河君 · 2026/10/31 9:08:43 · 阅读 1.2k 坐标压缩+BFS求稀疏障碍网格连通区域面积
这道题我第一次看到的时候题面其实没写完停在正方形草地位于直角坐标系中就断了。但就这半句话已经足够让我判断出它属于哪一类问题大坐标、稀疏障碍、求连通区域面积。这类题在区域赛和各类在线评测里反复出现套路非常固定可变的部分只有障碍长什么样和怎么走。下面我按自己解题和给队友讲题的顺序把这道懒羊羊吃青草完整拆一遍从题意还原到代码实现再到踩过的坑。1. 题意还原与建模先把草原变成一张图拿到一个不完整的题面第一步不是急着写代码而是把自然语言描述翻译成机器能处理的结构。这道题的场景很具体一只很能吃的羊一块巨大的正方形草地若干已经布好的陷阱问它能吃到多少草。翻译成算法语言就是在一个带障碍的区域内求从起点出发的可达区域大小。1.1 正方形草地的三种给法与互相转换正方形在直角坐标系里的给法常见的有三种我按出现频率排一下给左下角和边长、给四个顶点、给中心点和边长。这三种形式在代码里的处理差别不大核心都是先算出minx, miny, maxx, maxy四个值让整个问题回到轴对齐矩形这个最舒服的形态。如果给的是左下角(x0, y0)和边长L那四个边界直接就是x0、x0L、y0、y0L。我习惯把右边界和上边界记成开区间也就是格子只取到x0L-1这样后面算宽度的时候不用到处1少一半的差一错误。如果给的是四个顶点必须先验证它们真的是轴对齐的正方形判断方式很朴素所有点的 x 只有两种取值y 也只有两种取值并且 x 的跨度等于 y 的跨度。这一步不验证后面坑会埋得很深——万一给的是旋转 45 度的正方形那整个按列切分的思路直接作废得换成旋转坐标系或者几何方法。提醒一句如果题目的正方形是斜着放的坐标压缩那一套就不适用了。判断方法很简单看顶点坐标是不是只有两个不同的 x 值。我给一个小的转换片段把四顶点形式统一成左下角加边长long long minx min({px[0], px[1], px[2], px[3]}); long long maxx max({px[0], px[1], px[2], px[3]}); long long miny min({py[0], py[1], py[2], py[3]}); long long maxy max({py[0], py[1], py[2], py[3]}); // 这里必须断言 maxx - minx maxy - miny long long L maxx - minx;统一之后草地就是列号从x0到x0L-1、行号从y0到y0L-1的一张方格纸每个格子面积为单位 1。这一步做完后面所有的推导都只跟数字打交道跟羊和狼没关系了。1.2 陷阱到底是一个点、一个格子还是一堵墙这是这类题最容易产生歧义的地方也是题面写一半时最需要我自己拍板的地方。在连续平面上一个数学意义上的点是挡不住任何东西的羊可以从旁边绕过去绕着走能到达整个正方形答案就是L*L那这题就没意义了。所以陷阱只能理解为占据一个单位方格的实心块或者半径为 r 的圆形禁区。我按最常见、也最容易实现的那一种来建模陷阱(xi, yi)占据列xi、行yi的那个单位方格羊不能进入这个格子。这样问题就变成了标准的网格连通性问题四联通、八联通都可以按题目要求切换。如果你的原始题目里给的是陷阱的影响半径r那建模方式要换一下障碍不再是格子而是以陷阱为圆心、半径r的圆。这时候能不能穿过两个陷阱之间就变成了判断两圆之间有没有缝隙答案依赖dist(p1, p2) 2r这样的条件。这已经偏向计算几何跟坐标压缩是两个方向。我在第 7 节会简单提一下这种变体怎么处理。建模假设一定要在解题开头写清楚。我见过太多人代码写完了才发现自己对陷阱的理解跟出题人不一样白写两小时。1.3 懒羊羊的移动规则决定了算法内核能吃到的草这句话背后其实藏着两个必须明确的东西羊怎么走以及草怎么算。走法上最常见的是四联通上下左右也有题目要求八联通含对角线还有一类是只能沿直线走到底遇到陷阱或边界才转向。前两种是标准的 BFS/DFS 连通块问题第三种就变成了图形学里的光线投射或者可视图问题复杂度完全不是一个量级。草的计量上如果草地是离散格子答案就是可达格子数如果草地是连续的那还得考虑羊的嘴巴宽度、吃草半径之类。按题面巨大的正方形草地这个措辞我倾向于离散格子模型因为连续模型下巨大这个形容词没有意义。所以整道题的核心就一句话在一张L × L的网格上去掉若干障碍格求起点所在连通块的大小。如果L只有一两千到这里就可以直接开写了。麻烦的是巨大这两个字。2. 为什么直接 BFS 会炸先算清楚规模再动手我在带新人的时候发现一个普遍现象看到网格 连通块手比脑子快queue一写vis数组一开提交然后 TLE 或者 MLE。问题出在没有先算规模。这道题里的L是巨大那到底多大2.1 朴素做法的复杂度账本朴素 BFS 的时间是O(L²)空间也是O(L²)。如果L 10³那是一百万个格子随便写都能过如果L 10⁵那是一百亿个格子内存直接爆到几十 GB跑一天也跑不完如果L 10⁹——这在这类题里非常常见因为出题人喜欢用10⁹来表示坐标范围——那就是10¹⁸个格子连想都不用想。关键的地方在于陷阱的数量n通常很小比如n ≤ 1000甚至n ≤ 100。一整片草原上就挖了几百个坑绝大部分区域是干净的、同质的可我们的算法却要为每一个格子单独开一个vis标记这就是典型的计算量和信息量严重不匹配。我一般用这样一个类比跟队友解释你要统计一张巨大的白纸上被几个墨点分割成了几块区域正确做法是盯着墨点看而不是拿放大镜一格一格扫。墨点只有几百个但纸有几亿个像素扫完纸早就天亮了。2.2 稀疏性到底省在哪把10⁹ × 10⁹的网格摊开看它的结构复杂度其实完全由陷阱决定。没有陷阱的时候整块草地就是一个连通块答案是L²一行代码搞定。有陷阱的时候陷阱把整块草地切成若干块而切法只跟陷阱之间的相对位置有关。具体一点说考虑所有陷阱的 x 坐标它们把[x0, x0L)这个区间切成了若干段。任意一段内部所有列的行为是完全一样的——要么全都是空的因为这一段里没有陷阱的 x 坐标要么全都是障碍列如果这一段就是某个陷阱的 x 坐标本身。既然行为一样就没必要一列一列地区分合并成一列块就行。y 方向同理。两个方向都合并之后原本10⁹ × 10⁹的网格就变成了(3n2) × (3n2)的压缩网格。n 1000的时候是3002 × 3002约九百万个节点BFS 跑起来毫无压力。这就是坐标压缩的全部思想一句话能说完但细节上有不少讲究。2.3 一个具体数字对比我列个表把朴素做法和压缩做法的差距摊开看这个表我经常直接贴在解题报告里方案时间空间L10⁹, n1000 时可行性朴素网格 BFSO(L²)O(L²)完全不可行逐行扫描线O(n² log n)O(n)可行但实现复杂坐标压缩 BFSO(n² log n)O(n²)直接可写约 9M 节点坐标压缩 并查集O(n² α)O(n²)也可行省一点常数从表里能看出来坐标压缩是性价比最高的选择实现难度中等代码量可控正确性容易论证调试的时候还能把压缩后的网格打印出来肉眼检查。这也是我推荐新手优先掌握这个套路的原因。3. 坐标压缩把十亿的网格折叠成三千坐标压缩coordinate compression这个词在算法竞赛里出现频率极高但很多人只会背模板不知道为什么要这么写。我把它的推导过程完整走一遍理解了之后参数怎么选、边界怎么处理都是自然推出来的。3.1 区间等价类哪些列可以合并先把问题形式化。设草地覆盖的列号集合是[x0, x0L)左闭右开共L列行号集合是[y0, y0L)。定义两个列a和b是等价的如果对任意一行y格子(a, y)和(b, y)的可通行状态完全相同。由于障碍只出现在陷阱所在的列且只在该列的一个具体行上所以判断等价只需要看这一列上有没有陷阱没有陷阱的列整列都是空的跟其他空列等价有陷阱的列只有陷阱那一行是障碍跟其他列不等价。于是所有列被分成两类一类是陷阱所在的列一共最多n个另一类是没有陷阱的列但它们在空间上被陷阱列切成若干段每段内部彼此等价。行方向完全对称。这就给出了压缩规则把每一段连续的等价列合并成一个超级列宽度等于这段的列数行方向同理。压缩后的每个节点是一个矩形块面积就是宽度乘高度。3.2 关键点怎么选才不出漏合并的关键是找出分界点也就是那些必须单独成段的坐标。我的做法是对每个陷阱(x, y)往关键点集合里塞三个 x 值——x-1、x、x1y 方向同理。再加上草地本身的左右边界x0和x0L。为什么是三个而不是一个这里说三个理由每一个都对应一类容易出的错。第一个理由x本身必须加否则陷阱所在的列会被并进一个宽块里障碍就丢了。第二个理由x1必须加否则陷阱那一列会和右边一大片空列合并导致压缩后的陷阱格子宽度大于 1画出来的墙变厚了面积就算多了。加了x1之后陷阱格子一定是[x, x1)这样宽度恰好为 1 的格子跟原网格一一对应。第三个理由x-1严格来说不是必需的加不加不改变连通性结论。但我还是习惯加上因为它能让陷阱左侧那一列也独立出来调试的时候打印压缩网格人眼能跟原坐标直接对齐省掉很多脑补。另外如果题目后面追加陷阱有半径 1 的影响范围这种条件x-1就是必需的了。伪代码长这样vectorlong long xs, ys; xs.push_back(x0); xs.push_back(x0 L); ys.push_back(y0); ys.push_back(y0 L); for (auto [x, y] : traps) { if (x x0 || x x0 L || y y0 || y y0 L) continue; // 草地外的陷阱直接忽略 add(xs, x - 1, x0, x0 L); add(xs, x, x0, x0 L); add(xs, x 1, x0, x0 L); // y 方向同理 }注意add里的范围裁剪加进去的坐标必须在[x0, x0L]之内因为压缩网格只在草地范围内有意义。如果不裁边界外的坐标会凭空多出一段区间最后 BFS 会跑到草地外面去答案偏大。3.3 面积权重为什么不能只数格子压缩之后每个压缩格子代表原网格中的一片矩形区域面积是(xs[i1] - xs[i]) * (ys[j1] - ys[j])。BFS 访问到一个压缩格子时累加的是这个乘积而不是1。这一步是新手最容易写错的地方。我见过有人把压缩格子当普通格子每个格子加 1最后答案永远等于压缩网格的节点数跟真实面积差了几万倍。也见过有人只乘宽度不乘高度结果答案是一条斜线上的面积。用生活化的说法解释原来的网格是每个像素点大小一样的照片压缩之后变成了每块色块大小不一样的马赛克。你数色块个数没用得把每块色块的面积加起来。压缩的意义就在于同一块色块内部颜色一致要么全空要么全是障碍所以只需要判断一次。3.4 正确性说明压缩前后连通性真的等价吗这是必须要论证的一步不然写出来的代码自己心里都没底。命题在原网格中两个格子(a, b)和(c, d)四联通当且仅当它们所在的压缩格子(ia, jb)和(ic, jd)在压缩网格中四联通。充分性设压缩格子I和J相邻比如J在I右边。那么I的最右一列xs[i1]-1和J的最左一列xs[i1]在原网格中是相邻的两列。由于I和J都不是障碍格子这两列上对应的格子都可通行所以原网格中这两个格子相邻。这就说明压缩网格中的每条边在原网格中都能找到对应的边。必要性设原网格中(a, b)和(a1, b)相邻。如果它们属于同一个压缩格子那没什么好说的。否则a和a1之间必然存在一个关键点也就是a1是某个关键点那么(a, b)所在的压缩格子I和(a1, b)所在的压缩格子J满足xs[i1] a1即J是I的右邻居。所以压缩网格中也相邻。两个方向都成立连通性等价。这里有一个隐含条件必须满足压缩格子内部不能包含障碍。而我们的关键点选取保证了陷阱的 x 坐标一定是某个关键点所以陷阱所在的那一列一定是压缩格子的左边界任何包含陷阱的压缩格子宽度必然为 1内部不会再有第二条陷阱列。这个性质是整个论证的地基关键点选错地基就塌了。我调试这类题时有个固定动作把压缩后的网格打印成字符画障碍画#空地画.然后跟原网格的小样例逐格对照。这一步能抓出九成的错误。4. 动手实现离散化加 BFS 求连通块面积前面都是推导这一节进入代码。我把完整流程拆成四步读入与过滤、关键点收集与索引构建、障碍标记与起点定位、BFS 与面积累加。每一步都附上为什么要这么写。4.1 输入解析与陷阱过滤题面没给输入格式我按这类题的惯例定一个第一行x0 y0 L第二行n接下来n行每行一个陷阱坐标最后一行是起点sx sy。如果你的题目是给四个顶点的先按 1.1 节的方式转换一下。读入的时候要做两件事。第一件把草地范围外的陷阱丢掉。题目里经常出现灰太狼在草原上布陷阱严格说陷阱应该在草地内但输入数据里混进几个草地外的坐标是常事不做过滤的话关键点会跑到边界外压缩网格的结构就乱了。第二件重复的陷阱要去重。同一个格子放两个陷阱没有意义但不去重的话关键点会重复虽然unique之后不影响正确性但会让关键点数量虚高白白增加开销。long long X1 x0 L, Y1 y0 L; setpairlong long, long long trapSet; for (int i 0; i n; i) { long long x, y; cin x y; if (x x0 || x X1 || y y0 || y Y1) continue; trapSet.insert({x, y}); // 同时把 x-1, x, x1 和 y-1, y, y1 加入关键点 }用set存陷阱有个额外好处后面标记障碍时可以用O(log n)查询不过我们其实用不到查询因为陷阱坐标本身就保证是压缩网格某个格子的左下角直接lower_bound定位就行。4.2 关键点排序去重与索引映射关键点收集完之后必须排序去重。排序是为了让相邻两点构成一个区间去重是因为x-1、x、x1可能跟别的陷阱的关键点重合。sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); int W (int)xs.size() - 1; int H (int)ys.size() - 1;这里W和H是压缩网格的列数和行数。因为xs存的是边界点m个边界点围出m-1个区间所以要减 1。这一步减 1 忘了就是数组越界是仅次于差一错误的第二高频 bug。索引映射我建议用lower_bound现算不要提前开大数组存。原因很简单坐标是long long范围到10⁹甚至更大开数组存映射根本开不下。lower_bound每次O(log n)总调用次数是O(n)级别只有n个陷阱需要定位完全不影响复杂度。4.3 障碍标记与起点定位障碍标记很直接遍历陷阱集合用lower_bound找到它在xs和ys中的索引把压缩网格对应位置标成障碍。vectorvectorchar blocked(W, vectorchar(H, 0)); for (auto p : trapSet) { int i lower_bound(xs.begin(), xs.end(), p.first) - xs.begin(); int j lower_bound(ys.begin(), ys.end(), p.second) - ys.begin(); blocked[i][j] 1; }用char而不是bool是有讲究的。vectorbool是位压缩存储不能取地址很多场景下会出问题vectorchar每个元素 1 字节内存占用一样都是 1 bit 的逻辑对比 8 bit 的物理但访问速度更快也不会有各种诡异的编译问题。九百万个节点两个vectorchar也就 18 MB完全可以接受。起点定位稍微绕一点。起点坐标不一定恰好是关键点所以要用upper_bound找第一个大于起点的关键点再减 1 得到最后一个小于等于起点的关键点这就是起点所在的压缩列。int si (int)(upper_bound(xs.begin(), xs.end(), sx) - xs.begin()) - 1; int sj (int)(upper_bound(ys.begin(), ys.end(), sy) - ys.begin()) - 1;这里为什么不能用lower_bound举个例子xs [0, 5, 6, 10]起点sx 5。用lower_bound返回索引 1指向 5减 1 之后是 0那就跑到[0,5)这个区间去了错了。用upper_bound返回索引 2指向 6减 1 之后是 1正好对应[5,6)这个区间正确。这个坑我在比赛里踩过一次当时样例全过提交 WA 在第 7 个点查了四十分钟才发现是lower_bound和upper_bound搞反了。教训就是凡是找某个值所在的区间一律用upper_bound减一。定位完之后还要做三重检查起点是否在草地范围内、压缩索引是否越界、起点所在格子是不是障碍。三个检查缺一不可任何一个出问题都应该直接输出 0。4.4 BFS 主循环与面积累加BFS 本身没什么好讲的标准写法四个方向扩展。唯一需要注意的是面积累加的位置——在出队时累加而不是入队时。这样写的好处是每个节点只加一次不会因为重复入队而重复计算。当然如果入队时就标记vis效果是一样的。long long ans 0; queuepairint, int q; vis[si][sj] 1; q.push({si, sj}); const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1}; while (!q.empty()) { auto [i, j] q.front(); q.pop(); ans (xs[i 1] - xs[i]) * (ys[j 1] - ys[j]); for (int d 0; d 4; d) { int ni i dx[d], nj j dy[d]; if (ni 0 || ni W || nj 0 || nj H) continue; if (vis[ni][nj] || blocked[ni][nj]) continue; vis[ni][nj] 1; q.push({ni, nj}); } }ans必须用long long。面积最大可能到L²L 10⁹时是10¹⁸刚好在long long范围内9.2 × 10¹⁸但用int直接溢出成负数。这种溢出在本地小样例上永远测不出来只有大数据才会暴露所以从一开始就用long long别心疼那点内存。4.5 完整代码把所有部分拼起来就是可以直接提交的版本#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long x0, y0, L; if (!(cin x0 y0 L)) return 0; int n; cin n; long long X1 x0 L, Y1 y0 L; vectorlong long xs, ys; xs.push_back(x0); xs.push_back(X1); ys.push_back(y0); ys.push_back(Y1); auto addX [](long long v) { if (v x0 v X1) xs.push_back(v); }; auto addY [](long long v) { if (v y0 v Y1) ys.push_back(v); }; setpairlong long, long long trapSet; for (int i 0; i n; i) { long long x, y; cin x y; if (x x0 || x X1 || y y0 || y Y1) continue; trapSet.insert({x, y}); addX(x - 1); addX(x); addX(x 1); addY(y - 1); addY(y); addY(y 1); } long long sx, sy; cin sx sy; sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); int W (int)xs.size() - 1; int H (int)ys.size() - 1; vectorvectorchar blocked(W, vectorchar(H, 0)); for (auto p : trapSet) { int i (int)(lower_bound(xs.begin(), xs.end(), p.first) - xs.begin()); int j (int)(lower_bound(ys.begin(), ys.end(), p.second) - ys.begin()); blocked[i][j] 1; } if (sx x0 || sx X1 || sy y0 || sy Y1) { cout 0 \n; return 0; } int si (int)(upper_bound(xs.begin(), xs.end(), sx) - xs.begin()) - 1; int sj (int)(upper_bound(ys.begin(), ys.end(), sy) - ys.begin()) - 1; if (si 0 || si W || sj 0 || sj H || blocked[si][sj]) { cout 0 \n; return 0; } vectorvectorchar vis(W, vectorchar(H, 0)); queuepairint, int q; vis[si][sj] 1; q.push({si, sj}); long long ans 0; const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1}; while (!q.empty()) { auto [i, j] q.front(); q.pop(); ans (xs[i 1] - xs[i]) * (ys[j 1] - ys[j]); for (int d 0; d 4; d) { int ni i dx[d], nj j dy[d]; if (ni 0 || ni W || nj 0 || nj H) continue; if (vis[ni][nj] || blocked[ni][nj]) continue; vis[ni][nj] 1; q.push({ni, nj}); } } cout ans \n; return 0; }代码不长六十多行但每一行都有它存在的理由。我建议你自己手敲一遍别复制敲的过程中会自然去思考每一句为什么这么写比读十遍都管用。4.6 几类必须单独验证的边界情况写完代码先别提交拿下面这几组数据挨个跑一遍能提前抓掉大部分低级错误。场景输入特征期望行为没有陷阱n 0直接输出 L²不走 BFS 也对陷阱在草地外坐标超出范围过滤掉答案不受影响起点正好在陷阱上起点坐标与陷阱重合输出 0草地只有一格L 1压缩网格 1×1正确陷阱贴着边界x x0 或 x x0L-1关键点裁剪正确不越界陷阱把草地切成两半一排陷阱横贯只能吃到起点那一半起点在角落四角之一索引定位不越界陷阱重复给出同一坐标多次set 去重答案不变其中陷阱贴着边界和陷阱把草地切成两半这两个最值得反复测因为它们同时考验关键点裁剪和连通性判断出错的概率最高。5. 复杂度、内存与调优算法能跑对是一回事跑得快是另一回事。这一节把复杂度和资源占用量化一下方便你判断自己的实现在什么规模下是安全的。5.1 时间复杂度的完整推导整个过程分四步每步的复杂度单独看关键点收集是O(n)排序去重是O(n log n)因为关键点数量最多3n2障碍标记是n次lower_boundO(n log n)BFS 最多访问W × H个节点每个节点检查 4 条边O(n²)。总复杂度是O(n²)排序那一项被 BFS 的O(n²)吞掉了。n 1000时是9 × 10⁶次操作现代处理器一秒能做10⁸到10⁹次简单运算绰绰有余。n 5000时是2.25 × 10⁸就有点紧张了得看评测机性能。如果题目把n开到10⁵那O(n²)就彻底没戏了得换思路——通常是扫描线加并查集或者对陷阱做虚拟图上的 BFS只保留陷阱周围的O(n)个关键节点复杂度和陷阱之间的相邻关系有关。这类题会额外给出陷阱之间距离不小于某个值的约束正是为了让虚拟图的边数是O(n)的。5.2 内存占用的实际估算压缩网格的节点数是W × H最坏(3n2)²。n 1000时3002² ≈ 9 × 10⁶个节点。blocked和vis各占9 × 10⁶字节合计18 MB。队列最坏存9 × 10⁶个pairint,int每个 8 字节72 MB。加起来接近 100 MB如果内存限制是 64 MB 就悬了。几个优化方向按收益排序使用vectorint或一维数组代替vectorvectorchar减少嵌套容器的指针开销同时让内存连续缓存命中率更高。把队列换成手写的循环数组或者用vector当队列加两个指针省掉std::queue的deque开销。如果连通块不大可以在 BFS 结束后立刻swap释放vis不过这对峰值内存没帮助。我的经验是n ≤ 1000时不用优化直接写最清晰的版本n ≥ 3000时改成手写队列加一维数组再大就说明该换算法了优化常数救不了复杂度。5.3 几个能省时间的实现细节第一个是关闭同步流ios::sync_with_stdio(false); cin.tie(nullptr);输入量大的时候能省下可观的 I/O 时间。这个不是玄学实测差个两三倍很正常。第二个是用 BFS 而不是 DFS。DFS 在九百万节点的图上递归栈深可能达到百万级必然爆栈就算改成手写栈访问顺序也更不友好缓存命中率低。第三个是把blocked和vis合并成一个状态数组用 0 表示未访问、1 表示已访问、2 表示障碍这样只需要一次内存访问就能判断两种条件。这个优化在小数据上没感觉大数据上能省 10%~20% 的时间。6. 踩坑实录与排查清单这一节是我觉得整篇文章最有价值的部分。前面讲的都是正确的做法长什么样这一节讲我实际写错的时候错在哪。这些东西在学习资料里基本不会写只有真正提交过、WA 过、对拍过才会积累下来。6.1 常见错误速查表我把这些年在这类题上踩过的坑整理成表按出现频率排序你可以对照自己的代码逐条排查错误现象根因定位方式答案恒为 1 或很小面积累加忘了乘宽度/高度打印每步累加值答案接近 L² 但偏大陷阱没过滤跑到了草地外打印关键点数组段错误压缩网格索引越界少减 1检查 W、H 定义起点明明在空地上却输出 0lower_bound用错改upper_bound减 1小数据全过大数据 WAans用int溢出全部改long long障碍墙挡不住羊关键点漏了x1打印压缩网格比对多组数据后答案错乱全局数组没清空改成局部变量只有某个角落错边界坐标没裁剪检查addX范围判断表里前四条几乎覆盖了九成的错误。我特别说一下第二条答案偏大——这个坑很隐蔽因为如果所有陷阱都在草地内代码不会出问题只有题目数据里混了草地外的陷阱才会暴露。出题人有时是故意的用来区分有没有认真读数据范围。6.2 对拍最可靠的验证方式再自信的代码也要对拍。做法很简单写一个暴力版本用L ≤ 8的小网格直接BFS然后随机生成几千组数据跟压缩版对答案。暴力版的核心就是把草地老老实实展开成二维数组// 暴力版核心仅用于对拍 bool blocked[20][20]; bool vis[20][20]; int bfs(int sx, int sy, int L) { queuepairint, int q; vis[sx][sy] true; q.push({sx, sy}); int cnt 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); cnt; for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 0 || nx L || ny 0 || ny L) continue; if (vis[nx][ny] || blocked[nx][ny]) continue; vis[nx][ny] true; q.push({nx, ny}); } } return cnt; }对拍数据生成器要注意几个要点L取1到8陷阱数量0到L²陷阱坐标允许重复、允许超出范围测试过滤逻辑起点随机。这样几千组跑下来能覆盖绝大多数边界组合。我用这套方法