这道题我第一次看到的时候，题面其实没写完，停在"正方形草地位于直角坐标系中"就断了。但就这半句话，已经足够让我判断出它属于哪一类问题：大坐标、稀疏障碍、求连通区域面积。这类题在区域赛和各类在线评测里反复出现，套路非常固定，可变的部分只有"障碍长什么样"和"怎么走"。下面我按自己解题和给队友讲题的顺序，把这道"懒羊羊吃青草"完整拆一遍，从题意还原到代码实现，再到踩过的坑。
1. 题意还原与建模：先把草原变成一张图
拿到一个不完整的题面，第一步不是急着写代码，而是把"自然语言描述"翻译成"机器能处理的结构"。这道题的场景很具体：一只很能吃的羊，一块巨大的正方形草地，若干已经布好的陷阱，问它能吃到多少草。翻译成算法语言，就是在一个带障碍的区域内，求从起点出发的可达区域大小。
1.1 正方形草地的三种给法与互相转换
正方形在直角坐标系里的给法，常见的有三种，我按出现频率排一下：给左下角和边长、给四个顶点、给中心点和边长。这三种形式在代码里的处理差别不大，核心都是先算出minx, miny, maxx, maxy四个值，让整个问题回到"轴对齐矩形"这个最舒服的形态。
如果给的是左下角(x0, y0)和边长L，那四个边界直接就是x0、x0+L、y0、y0+L。我习惯把右边界和上边界记成"开区间"，也就是格子只取到x0+L-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到x0+L-1、行号从y0到y0+L-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, x0+L)这个区间切成了若干段。任意一段内部，所有列的行为是完全一样的——要么全都是空的（因为这一段里没有陷阱的 x 坐标），要么全都是障碍列（如果这一段就是某个陷阱的 x 坐标本身）。既然行为一样，就没必要一列一列地区分，合并成一"列块"就行。
y 方向同理。两个方向都合并之后，原本10⁹ × 10⁹的网格，就变成了(3n+2) × (3n+2)的压缩网格。n = 1000的时候是3002 × 3002，约九百万个节点，BFS 跑起来毫无压力。
这就是坐标压缩的全部思想，一句话能说完，但细节上有不少讲究。
2.3 一个具体数字对比
我列个表，把朴素做法和压缩做法的差距摊开看，这个表我经常直接贴在解题报告里：
| 方案 | 时间 | 空间 | L=10⁹, n=1000 时可行性 |
|---|---|---|---|
| 朴素网格 BFS | O(L²) | O(L²) | 完全不可行 |
| 逐行扫描线 | O(n² log n) | O(n) | 可行但实现复杂 |
| 坐标压缩 + BFS | O(n² log n) | O(n²) | 直接可写，约 9M 节点 |
| 坐标压缩 + 并查集 | O(n² α) | O(n²) | 也可行，省一点常数 |
从表里能看出来，坐标压缩是"性价比"最高的选择：实现难度中等，代码量可控，正确性容易论证，调试的时候还能把压缩后的网格打印出来肉眼检查。这也是我推荐新手优先掌握这个套路的原因。
3. 坐标压缩：把十亿的网格折叠成三千
坐标压缩（coordinate compression）这个词在算法竞赛里出现频率极高，但很多人只会背模板，不知道为什么要这么写。我把它的推导过程完整走一遍，理解了之后，参数怎么选、边界怎么处理，都是自然推出来的。
3.1 区间等价类：哪些列可以合并
先把问题形式化。设草地覆盖的列号集合是[x0, x0+L)（左闭右开，共L列），行号集合是[y0, y0+L)。
定义两个列a和b是"等价"的，如果对任意一行y，格子(a, y)和(b, y)的可通行状态完全相同。由于障碍只出现在陷阱所在的列（且只在该列的一个具体行上），所以判断等价只需要看这一列上有没有陷阱：没有陷阱的列，整列都是空的，跟其他空列等价；有陷阱的列，只有陷阱那一行是障碍，跟其他列不等价。
于是所有列被分成两类：一类是"陷阱所在的列"，一共最多n个；另一类是"没有陷阱的列"，但它们在空间上被陷阱列切成若干段，每段内部彼此等价。
行方向完全对称。
这就给出了压缩规则：把每一段连续的等价列合并成一个"超级列"，宽度等于这段的列数；行方向同理。压缩后的每个节点是一个矩形块，面积就是宽度乘高度。
3.2 关键点怎么选才不出漏
合并的关键是找出"分界点"，也就是那些必须单独成段的坐标。我的做法是：对每个陷阱(x, y)，往关键点集合里塞三个 x 值——x-1、x、x+1，y 方向同理。再加上草地本身的左右边界x0和x0+L。
为什么是三个而不是一个？这里说三个理由，每一个都对应一类容易出的错。
第一个理由，x本身必须加，否则陷阱所在的列会被并进一个宽块里，障碍就丢了。
第二个理由，x+1必须加，否则陷阱那一列会和右边一大片空列合并，导致压缩后的陷阱格子宽度大于 1，画出来的"墙"变厚了，面积就算多了。加了x+1之后，陷阱格子一定是[x, x+1)这样宽度恰好为 1 的格子，跟原网格一一对应。
第三个理由，x-1严格来说不是必需的，加不加不改变连通性结论。但我还是习惯加上，因为它能让陷阱左侧那一列也独立出来，调试的时候打印压缩网格，人眼能跟原坐标直接对齐，省掉很多脑补。另外如果题目后面追加"陷阱有半径 1 的影响范围"这种条件，x-1就是必需的了。
伪代码长这样：
vector<long 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, x0+L]之内，因为压缩网格只在草地范围内有意义。如果不裁，边界外的坐标会凭空多出一段区间，最后 BFS 会跑到草地外面去，答案偏大。
3.3 面积权重：为什么不能只数格子
压缩之后，每个压缩格子代表原网格中的一片矩形区域，面积是(xs[i+1] - xs[i]) * (ys[j+1] - ys[j])。BFS 访问到一个压缩格子时，累加的是这个乘积，而不是1。
这一步是新手最容易写错的地方。我见过有人把压缩格子当普通格子，每个格子加 1，最后答案永远等于压缩网格的节点数，跟真实面积差了几万倍。也见过有人只乘宽度不乘高度，结果答案是一条斜线上的面积。
用生活化的说法解释：原来的网格是"每个像素点大小一样"的照片，压缩之后变成了"每块色块大小不一样"的马赛克。你数色块个数没用，得把每块色块的面积加起来。压缩的意义就在于：同一块色块内部颜色一致（要么全空要么全是障碍），所以只需要判断一次。
3.4 正确性说明：压缩前后连通性真的等价吗
这是必须要论证的一步，不然写出来的代码自己心里都没底。
命题：在原网格中，两个格子(a, b)和(c, d)四联通，当且仅当它们所在的压缩格子(ia, jb)和(ic, jd)在压缩网格中四联通。
充分性：设压缩格子I和J相邻（比如J在I右边）。那么I的最右一列xs[i+1]-1和J的最左一列xs[i+1]在原网格中是相邻的两列。由于I和J都不是障碍格子，这两列上对应的格子都可通行，所以原网格中这两个格子相邻。这就说明压缩网格中的每条边，在原网格中都能找到对应的边。
必要性：设原网格中(a, b)和(a+1, b)相邻。如果它们属于同一个压缩格子，那没什么好说的。否则a和a+1之间必然存在一个关键点，也就是a+1是某个关键点，那么(a, b)所在的压缩格子I和(a+1, b)所在的压缩格子J满足xs[i+1] = a+1，即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; set<pair<long 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, x+1 和 y-1, y, y+1 加入关键点 }用set存陷阱有个额外好处：后面标记障碍时可以用O(log n)查询，不过我们其实用不到查询，因为陷阱坐标本身就保证是压缩网格某个格子的左下角，直接lower_bound定位就行。
4.2 关键点排序去重与索引映射
关键点收集完之后，必须排序去重。排序是为了让相邻两点构成一个区间，去重是因为x-1、x、x+1可能跟别的陷阱的关键点重合。
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中的索引，把压缩网格对应位置标成障碍。
vector<vector<char>> blocked(W, vector<char>(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是有讲究的。vector<bool>是位压缩存储，不能取地址，很多场景下会出问题；vector<char>每个元素 1 字节，内存占用一样（都是 1 bit 的逻辑对比 8 bit 的物理），但访问速度更快，也不会有各种诡异的编译问题。九百万个节点，两个vector<char>也就 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; queue<pair<int, 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; vector<long 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); }; set<pair<long 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; vector<vector<char>> blocked(W, vector<char>(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; } vector<vector<char>> vis(W, vector<char>(H, 0)); queue<pair<int, 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 = x0+L-1 | 关键点裁剪正确，不越界 |
| 陷阱把草地切成两半 | 一排陷阱横贯 | 只能吃到起点那一半 |
| 起点在角落 | 四角之一 | 索引定位不越界 |
| 陷阱重复给出 | 同一坐标多次 | set 去重，答案不变 |
其中"陷阱贴着边界"和"陷阱把草地切成两半"这两个最值得反复测，因为它们同时考验关键点裁剪和连通性判断，出错的概率最高。
5. 复杂度、内存与调优
算法能跑对是一回事，跑得快是另一回事。这一节把复杂度和资源占用量化一下，方便你判断自己的实现在什么规模下是安全的。
5.1 时间复杂度的完整推导
整个过程分四步，每步的复杂度单独看：
关键点收集是O(n)；排序去重是O(n log n)，因为关键点数量最多3n+2；障碍标记是n次lower_bound，O(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，最坏(3n+2)²。n = 1000时，3002² ≈ 9 × 10⁶个节点。
blocked和vis各占9 × 10⁶字节，合计18 MB。队列最坏存9 × 10⁶个pair<int,int>，每个 8 字节，72 MB。加起来接近 100 MB，如果内存限制是 64 MB 就悬了。
几个优化方向，按收益排序：
使用vector<int>或一维数组代替vector<vector<char>>，减少嵌套容器的指针开销，同时让内存连续，缓存命中率更高。把队列换成手写的循环数组，或者用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 定义 |
| 起点明明在空地上却输出 0 | lower_bound用错 | 改upper_bound减 1 |
| 小数据全过，大数据 WA | ans用int溢出 | 全部改long long |
| 障碍"墙"挡不住羊 | 关键点漏了x+1 | 打印压缩网格比对 |
| 多组数据后答案错乱 | 全局数组没清空 | 改成局部变量 |
| 只有某个角落错 | 边界坐标没裁剪 | 检查addX范围判断 |
表里前四条几乎覆盖了九成的错误。我特别说一下第二条"答案偏大"——这个坑很隐蔽，因为如果所有陷阱都在草地内，代码不会出问题；只有题目数据里混了草地外的陷阱才会暴露。出题人有时是故意的，用来区分"有没有认真读数据范围"。
6.2 对拍：最可靠的验证方式
再自信的代码也要对拍。做法很简单：写一个暴力版本，用L ≤ 8的小网格直接BFS，然后随机生成几千组数据，跟压缩版对答案。
暴力版的核心就是把草地老老实实展开成二维数组：
// 暴力版核心，仅用于对拍 bool blocked[20][20]; bool vis[20][20]; int bfs(int sx, int sy, int L) { queue<pair<int, 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²，陷阱坐标允许重复、允许超出范围（测试过滤逻辑），起点随机。这样几千组跑下来，能覆盖绝大多数边界组合。
我用这套方法
