第一次把“战胜白蚁”丢进评测机跑通的时候，我盯着屏幕上绿色的AC看了好几秒。这是2024年全国信息素养大赛C++赛道的一套高质量模拟题，题面包装得像一个塔防小游戏：矩形领地上散布着白蚁巢穴，你只能在开战前布置防御炮台，白蚁群按秒向四个方向蔓延，问最少需要多长时间才能把蚁群完全清空。很多学生看到这个题的第一反应是“这要写个搜索吧”，然后就开始硬模拟，最后提交上去要么超时，要么结果差一点。实际这道题真正考的是图遍历、队列、二分答案和边界控制这些C++基本功，题目把算法藏在了一个故事下面。这篇文章就把我当时备赛的完整拆解过程写出来，从题目建模、算法选型、代码实现到常见坑点都有，想备战信息素养大赛，或者准备蓝桥杯、CSP这类竞赛的同学，都拿它当个参考。
1. 题目复盘：这道题到底在考什么
1.1 先还原一下题面模型
竞赛题虽然没有完全公开的标准题面，但从备赛训练中的版本来看，“战胜白蚁”的模型大概是这样的：给你一张n * m的地图，地图上有若干个白蚁巢穴作为扩散起点，每秒白蚁会向上、下、左、右四个相邻格子扩散一格。你可以在开战前选定一些格子布置防御炮台，每个炮台有固定的攻击半径，开战后会持续清剿进入攻击范围内的白蚁。题目要求的是：在所有炮台位置确定的前提下，能够把全部白蚁清剿干净的最短时间是多少。
这道题本质上是一个“带防御设施的感染扩散模拟”。把白蚁群想象成火灾蔓延，炮台是消防队，你要算的是火多久能被扑灭。有了这个具象化的理解之后，题目就不再是“打游戏”，而是一个可以用算法精确计算的离线决策问题。
1.2 它为什么是信息素养大赛的“压轴脸”
全国信息素养大赛C++赛道的题目设置，跟纯粹的ACM竞赛有一点不同：它很看重把实际问题转化成代码的能力，而不是只比谁数据结构背得熟。“战胜白蚁”恰恰就把二维网格、多源扩散、最优化时间这三个要素全部装进了一个看似游戏化的外壳里。
这种题目对选手有两个要求：一是能看穿包装，识别出“扩散”对应BFS，“最少时间”对应二分答案；二是有扎实的C++基本功，能在规定时间内把模型写成不崩、不超时的代码。很多人在考场上一看题面很长，心里就开始发怵，实际上只要你把题干里的动作拆成“扩散”和“攻击”两类，思路一下就清楚了。
1.3 审题时最容易踩的误区
我帮学生复盘的时候发现，半数以上的人第一步就理解偏了。他们以为炮台是开战后可以移动或临时补建的，于是写了一个类似实时策略游戏的循环：每秒钟先判断哪里要被围攻，然后把炮台挪过去。这其实是把一道离线最优化问题做成了在线贪心，题目里明确规定“开战前布置”，后续不能调整。
另一类误区是混淆攻击半径：炮台攻击范围是欧几里得距离，还是曼哈顿距离？这个必须看题面给的定义。很多学生默认按格子周围一圈计算，把r=2理解成十字范围，结果样例能过，大数据全挂。这就是典型的没把规则写进代码模型里，而是一开始就在脑子里面脑补规则。
2. 算法选型与建模：为什么绕不开BFS和二分
2.1 把地图抽象成状态集合
处理这类问题的第一步，是把地图变成程序能懂的二维网格。我习惯用一个vector<vector<char>>存原始地图，其中.表示空地，#表示障碍物，S表示白蚁起点，T表示炮台位置。另外再开一个二维数组记录每个格子被白蚁覆盖的时间，或者记录当前轮次是否已经被扩散到。
这里有个细节需要提一下：起点可能有多个。多个白蚁巢穴同时往外扩散，这就是典型的多源BFS，处理办法很简单——初始化队列时把所有起点一次性放进去。后面每一轮扩展，从队列头部弹出格子，向四个方向尝试走一步，只要没有越界、不是障碍物、且当前格子还没有被访问过，就标记访问并入队。
2.2 扩散动作为什么天生适合用队列
BFS（广度优先搜索）的核心特点是“按层扩展”，这和白蚁按秒扩散的节奏完全对应。同一批次被扩散到的格子，属于同一个时间层，从这些格子再往外扩展一步，消耗的时间正好加1。如果你用DFS（深度优先搜索）去写，递归深度在地图比较大的时候会爆栈，而且层数关系很难精确映射到“秒”上。
这里我多说一句队列的实现。竞赛里我优先用std::queue，不过如果你的开发环境编译器版本比较老旧，注意queue的头文件需要显式包含。方向数组推荐这样写：
int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1};四个方向对应上、下、左、右，顺序无所谓，只要保证每次四个方向都遍历到就行。用for (int k = 0; k < 4; k++)去枚举，代码简洁，也避免一份一份复制四次带来的低级错误。
2.3 最优时间求解：二分答案是个老朋友
直接模拟有个致命问题：如果清剿完成需要几十万秒，地图又大，每秒钟把白蚁群整体扩展一遍，复杂度会高到无法接受。我们需要的其实是“最短清剿时间”，这个值天然满足单调性：给定一个时间t，如果能在t秒内清剿完，那么比t更大的时间也一定能清剿完。看到这种“最小可行值”，就应该条件反射想到二分答案。
二分答案的套路很固定：下界设为0，上界设为地图最长边长加白蚁扩散所需的最大理论时间，或者直接设成一个比较大的数，比如n * m + 5。每次取中间值mid，跑一个check(mid)函数判断在mid秒内能否把白蚁全部消灭。如果能，就收缩右边界，否则收缩左边界。循环结束后left就是答案。
这样做的动机很明确：我们把一个“模拟过程求时间”的问题，变成了“固定时间判断是否可行”的问题。后者每次操作的空间复杂度是O(n*m)，配合二分只需要跑大约log(最大值)次，整体非常快。
2.4 复杂度估算：不见得非要跑满全图
直接模拟的最坏情况是什么？假设地图是1000 * 1000，白蚁从角落出发，炮台在另一个角落，白蚁需要扩散大约2000秒才能覆盖到炮台射程，这个量级还能接受。但如果题目把初始_blank白蚁起点设计成相隔很远的多个巢穴，并且清剿判定需要等待扩散覆盖全图，时间就可能来到数万秒。每一秒都做一次全图扫描，就是O(T * n * m)，当T达到几万时，T * n * m就会冲到几十亿甚至上百亿次操作，评测机没法在限定时间内跑完。
这也是我推荐“BFS做扩散 + 二分答案控制检查次数”的核心原因。check函数里用一次BFS完成mid秒的扩散模拟，然后统计炮台覆盖范围内是否还有活蚁，每次检查的复杂度是O(n*m)，二分只做log(maxT)次，比如maxT=100000时只需要17次左右，整体复杂度大约O(n*m*log(maxT))，稳得很。
3. 核心代码实现：C++关键语法逐个敲一遍
3.1 二维数组、字符串数组和结构体初始化
很多初学者写这道题，第一段代码还没开始写搜索，就先被初始化绊倒了。二维数组如果你确定最大尺寸，可以用char grid[1005][1005];这种静态数组，但最好用memset初始化，否则上一组测试数据的残留值会影响判断。如果你更喜欢动态分配，就用vector：
vector<vector<char>> grid(n, vector<char>(m, '.'));这行代码的含义是：创建一个n行、每行有m个字符的二维vector，每个元素初始化为.。这里有一个容易忽略的点：vector<vector<char>>两个>之间在旧标准里需要空格写成> >，否则部分编译器可能解析成右移运算符。虽然现代C++11已经修复了这个问题，但比赛环境如果用的编译器比较老，建议还是空格隔开，省得编译报错时一脸懵。
字符串数组初始化同样有很多坑。用字符数组存字符串时，记得要给结尾的\0留位置。比如存一个长度为10的字符串，数组长度至少是char s[11]。还有，string s = "abc";和char s[4] = "abc";在使用习惯上差异很大：前者可以直接s.length()、s[i]，后者必须自己注意长度和结尾符。竞赛里我更推荐用std::string处理所有和文本有关的输入，能省掉大量strcpy、strcmp带来的隐患。
至于结构体，如果你需要把“某个格子的坐标 + 到达时间”打包放进队列，定义一个结构体会让代码清晰很多：
struct Node { int x, y, step; };注意结构体变量列表初始化的时候，顺序必须和声明一致，不要写反了x和y，这种错误编译器不会提示，只能靠你检查数据流时发现。
3.2 BFS的标准动作：队列、方向数组与访问标记
BFS写多了你会发现所有这类题目都是同一个骨架：建队列、起点入队、标记访问、循环取队首、扩展四个方向、合法就入队。下面这段代码是参考实现：
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; char mp[MAXN][MAXN]; int dist[MAXN][MAXN]; int n, m; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; bool bfs(vector<pair<int,int>>& starts, int limit) { queue<pair<int,int>> q; memset(dist, -1, sizeof(dist)); for (auto& p : starts) { q.push(p); dist[p.first][p.second] = 0; } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); if (dist[x][y] >= limit) continue; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (mp[nx][ny] == '#') continue; if (dist[nx][ny] != -1) continue; dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } // 在 limit 秒内所有被扩散到的格子，dist 不为 -1 return true; }这段代码里我把limit作为参数传进BFS，表示最多扩散多少秒。dist数组用来记录每个格子的最早扩散时间，初始化为-1，这样天然就起到了“是否访问过”的标记作用。队列里存pair<int,int>，组合了横纵坐标，简单直接。
如果你用的是std::pair，记得q.push({nx, ny});这种花括号初始化在C++11之后才支持。部分老比赛环境可能不支持，那就老老实实q.push(make_pair(nx, ny));。
3.3 暴力BFS模拟版本：先保证能算对
拿到一道题，第一版代码我永远建议先写一个逻辑最简单、能跑出正确结果的版本，哪怕它慢。这样你可以拿它和后面的优化版对拍。暴力版本的思路是：每秒钟让所有存活的白蚁向四周扩展，同时统计炮台射程内还有没有白蚁。当某一次扩散后，所有白蚁都在炮台攻击范围内且没有新增扩散目标，就认为清剿完成。
int simulate(vector<pair<int,int>>& starts, vector<pair<int,int>>& towers, int r) { queue<Node> q; memset(dist, -1, sizeof(dist)); for (auto& p : starts) { q.push({p.first, p.second, 0}); dist[p.first][p.second] = 0; } int total = starts.size(); int ans = 0; while (!q.empty()) { Node cur = q.front(); q.pop(); bool killed = false; for (auto& t : towers) { int dd = abs(cur.x - t.first) + abs(cur.y - t.second); if (dd <= r) killed = true; } if (killed) continue; ans = max(ans, cur.step); for (int k = 0; k < 4; k++) { int nx = cur.x + dx[k]; int ny = cur.y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (dist[nx][ny] != -1) continue; dist[nx][ny] = cur.step + 1; q.push({nx, ny, cur.step + 1}); } } return ans; }注意上面这个暴力版本把“被炮台覆盖的白蚁”直接视作不再扩展，这是一个简化模型，实际题面如果要求“被覆盖前已经扩散的格子仍会扩散”，那判断逻辑要调整。这里我想强调的是：abs函数在C++里位于<cstdlib>或<cmath>，很多选手在代码开头只写了#include <iostream>，用abs的时候会编译报错，写上#include <bits/stdc++.h>这种竞赛万能头文件最省心。
3.4 二分+check优化版本：正式代码的正确打开方式
暴力版本最容易超时的点就是“每一秒都统计全图炮台覆盖”。优化做法就是前面说的二分答案。check函数要做两件事：第一，用BFS让白蚁扩散mid秒；第二，遍历所有被扩散到的格子，检查它们是否都在某个炮台的攻击范围内。
bool check(int mid, vector<pair<int,int>>& starts, vector<pair<int,int>>& towers, int r) { queue<pair<int,int>> q; memset(dist, -1, sizeof(dist)); for (auto& p : starts) { q.push(p); dist[p.first][p.second] = 0; } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); if (dist[x][y] >= mid) continue; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (mp[nx][ny] == '#') continue; if (dist[nx][ny] != -1) continue; dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (dist[i][j] == -1) continue; bool safe = false; for (auto& t : towers) { if (abs(i - t.first) + abs(j - t.second) <= r) { safe = true; break; } } if (!safe) return false; } } return true; }主函数里二分的时候，我建议把上界设大一点，比如n * m + 100，这样保证答案一定落在区间内。二分循环的终止条件用left < right，每次mid = (left + right) / 2，注意整型二分防止死循环，在right - left只差1时谨慎处理，一般写成while (left < right)配合left = mid + 1或right = mid就没问题。
int left = 0, right = n * m + 100; while (left < right) { int mid = (left + right) / 2; if (check(mid, starts, towers, r)) right = mid; else left = mid + 1; } cout << left << "\n";这段代码的巧妙之处在于：check函数内部的时间复杂度是O(n*m + 炮台数量*n*m)，如果炮台数量特别大，你还可以预处理一个“炮台覆盖矩阵”，提前用BFS或距离计算标记哪些格子是被覆盖的，check时直接查表，省去遍历炮台的开销。这个优化在炮台数量大于100时会比较明显。
4. 从“战胜白蚁”延伸开的高频C++考点
4.1 排序不能只会冒泡
热度词里“冒泡排序算法c++”和“归并排序c++”出现频率很高，说明很多初学者都在一边练算法一边记语法。我的建议是：冒泡排序可以作为理解“比较与交换”概念的教学案例，但真正写题时不要手写它，直接用std::sort。sort底层是经过优化的混合排序，数据量大时用快排，数据量小时退化为插入排序，性能远好于你自己手写的冒泡。
如果题目要求稳定排序，比如按照某个键值排序且相同键值要保持原顺序，就用std::stable_sort。归并排序则需要你理解“分治合并”的思路，因为它是求逆序对数量的核心工具。做题时遇到“稳定”“逆序对”这类字眼，再把手写归并捡起来。
4.2 字符串与数组初始化的经典陷阱
“c++字符串数组初始化”和“c++字符串转数组”也是高频搜索，因为很多人总是在这里报错。我建议记住几条铁律：第一，char s[100]声明后如果不赋初值，里面是随机垃圾，用之前必须memset(s, 0, sizeof(s));或者定义时就写成char s[100] = {0};。第二，std::string转字符数组用s.c_str()，转int用stoi(s)，转long long用stoll(s)，这些函数在C++11里都有，比赛环境一般支持。
还有一个容易被忽略的“c++字符串转数组”场景：如果你要把一个字符串按分隔符拆成多个整数，不建议手写循环判断，直接用stringstream配合getline更整洁，也可以用std::istringstream。但是注意，stringstream在处理大量数据时性能一般，如果是百万级别的转换，建议用std::stoi配合手工遍历。
4.3 栈空间与递归：深搜为什么会崩
“c++ 栈空间”上了热搜，说明很多新手遇到过程序运行崩溃，但不知道为什么。程序里每调用一次函数，系统会为这次调用分配一块栈内存，里面放着局部变量、参数和返回地址。正常情况下几万层递归就会把默认栈空间耗尽，表现就是Segmentation fault。
“战胜白蚁”如果不想用BFS，有人会尝试DFS递归遍历扩散路径，在小地图上可能没问题，一旦地图变成1000*1000，递归深度最大可能达到1000000层，直接爆栈。这也就是为什么我前面坚持用队列实现BFS，而不是用递归DFS。如果确实需要深搜，可以考虑把递归改成显式栈，或者把dfs函数内的局部大数组放到全局变量。全局变量和静态变量在数据段，不占栈空间，这是一个很重要的保命技巧。
4.4 工程与竞赛的差异：多线程、智能指针和工业应用
热度词里出现了“c++多线程”“unique_ptr”“OpenCV”“UG二次开发”这些工程向内容，说明很多人在刷竞赛题的同时也在接触真实项目。竞赛代码和工程代码有一个很大的区别：竞赛追求短平快，不在乎内存泄漏，因为程序跑完就退出；工程则必须关心资源管理，智能指针就派上了用场。比如用std::unique_ptr<char[]>管理动态字符数组，能省去手动delete[]的烦恼。
如果你以后做UG二次开发、OpenCV图像处理这类C++工业项目，竞赛里训练出来的“拆解问题、设计数据结构、控制复杂度”能力依然是最核心的竞争力。区别只在于工程更讲究代码可读性、异常安全和调试便捷性。所以别觉得竞赛只是刷题，它真正训练的是你面对复杂问题的抽象拆解能力。
5. 备赛环境与工具链配置
5.1 VSCode配置C/C++环境的关键点
很多同学对“vscode配置c/c++环境”特别头疼，明明装好了一堆插件，一按F5还是报错。我按实际经验说几个最容易踩的坑：第一，编译器不是VSCode自带的，需要自己装MinGW-w64，装完后把bin目录加进系统PATH，命令行里执行g++ --version能输出版本号才算成功。第二，tasks.json里的args要包含-g和-o，分别表示生成调试信息和指定输出文件。第三，launch.json里的miDebuggerPath指向gdb.exe的完整路径，路径里不能有中文，否则调试器起不来。
配置完成后，我建议先写一个hello.cpp，用F5跑通调试，再开始写竞赛题。开发环境没有调通就急着写大程序，遇到编译错误时会把环境问题和代码问题混在一起，排查起来加倍痛苦。
5.2 Dev-C++、运行库与比赛环境
热度词里还有“dev c++ 官网”和“microsoft visual c++ redistributable”，这其实是两个完全不同层面的东西。Dev-C++是一个老牌IDE，界面简单，适合新手，但它的默认编译器版本通常很老，对一些新标准支持不够好，用的时候把编译器设置改成C++14或C++17。Visual C++ Redistributable是程序运行所需的运行库，比赛评测机的Windows系统里有没有装这个运行库，直接决定你本地编译出来的exe能否在评测机上正常启动。
我个人的习惯是：比赛提交源代码，专注让代码在评测平台上通过；如果是线下比赛需要提交可执行文件，赛前一定先搞清楚比赛机器装了什么运行库、编译器版本是多少，不要等到现场才发现跑不起来。
5.3 用freopen和日志输出做调试
调试竞赛代码我有一个很好用的小技巧：数据量大的时候不要用断点调试，直接用freopen把输入输出重定向到文件，然后用printf或cerr往中间过程打日志。cerr输出到标准错误流，和答案输出分离，你在日志里能看到每一轮的BFS队列状态和dist数组变化，定位逻辑错误特别快。
freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);写完正式提交前，把这两行注释掉，别带着文件重定向直接交到评测系统。我见过不少学生，本地跑得好好的，评测机一跑就是“Runtime Error”，最后一查是忘了注释freopen，评测环境没有这个输入文件，程序直接读不到内容崩溃了。
6. 常见问题与排查技巧实录
6.1 评测超时的三个常见原因
第一个是输入输出没有加速。很多题的数据量很大，cin默认要和C标准IO同步，以保证scanf和cin混用时顺序一致，代价就是慢。加了下面两行，速度能提升好几倍：
ios::sync_with_stdio(false); cin.tie(nullptr);第二个原因是重复BFS。比如二分答案里你对同一个地图跑了17次check，每次check里又反复扫描全图，这时候要检查是否可以通过预处理访问矩阵来减少重复计算。第三个原因是把最内层循环写进去了不必要的判断或函数调用，比如在for循环里反复调用pow或sqrt计算距离，这些函数开销很大，完全可以用整数平方比较替代。
6.2 边界数据怎么构造
我的习惯是，代码写完第一件事不是直接交，而是先自己造几组边界数据：“单行单列地图”、“白蚁起点被障碍物包围”、“炮台覆盖全图”、“没有任何炮台”、“地图全是障碍物”。每组数据都要明确答案是多少。比如地图是1*1，起点也是炮台覆盖范围内，答案应该是0；如果没有任何炮台，答案应该是白蚁扩散全图所需时间。造边界数据这个动作花不了两分钟，但能帮你拦下大量低级错误。
6.3 本地正确但线上错误怎么查
这种问题是最磨人的。常见原因有三类：第一，数组越界。你的数组开的是MAXN，但输入里给的n超过了MAXN，本地可能因为内存布局侥幸没崩，评测机上一跑就挂。直接用vector动态分配，或者把MAXN开到比题目上限大10，是更稳妥的做法。第二，多组测试数据之间没有清理全局状态。dist、vis数组必须重新初始化，queue必须声明在函数内部。第三，using namespace std;引发的命名冲突，比如你定义了一个变量名叫data，在某些编译器版本里可能跟标准库内部名字冲突，解决办法是不要用常见关键字做变量名。
6.4 考场上的保命策略
如果正式比赛遇到完全没思路的难题，我建议先把暴力版本写出来，哪怕只能拿部分分数也要先拿到手。信息素养大赛的数据通常分多个子任务，暴力版本能过掉小数据，优化版本再慢慢写。在写优化版本之前，保留一份暴力版本代码，这样你还能拿它跟优化版本跑对拍。对拍的正确姿势是：写一个随机数据生成器，然后不停跑暴力版和优化版，直到发现结果不同，再用小数据手工分析哪里出了问题。这个流程看起来麻烦，但比你在评测系统上反复交答案高效得多。
我后来帮学生复盘这道“战胜白蚁”的时候，发现大家真正卡住的往往不是BFS写不出来，而是从“知道要搜索”到“知道要怎么搜索”中间差的那一步建模能力。一个网格，一堆起点，一个扩散规则，一个时间判定，这四个零件单独拿出来都不难，组合在一起就需要你有一套稳定的解题框架。我把这套框架总结成五个字：建模、搜索、二分、验证、优化。每次遇到新题都先问自己：状态空间是什么，扩展规则是什么，判定条件是什么，复杂度能不能接受。按这个顺序走下来，大部分看起来花里胡哨的模拟题都能稳稳拆掉。
最后再分享一个小技巧。备赛阶段每做完一道题，我都建议你在自己的错题本上记录三件事：第一，这道题的考点标签是什么；第二，你在哪一步卡住了；第三，下次遇到类似题目的第一反应应该是什么。坚持一个月，你回头再看这些记录，会发现自己对算法的敏感度提升得非常明显。希望这篇复盘也能帮你在信息素养大赛或者任何一场C++竞赛里，少踩几个坑，多拿一点分。
