第一次把“战胜白蚁”丢进评测机跑通的时候我盯着屏幕上绿色的AC看了好几秒。这是2024年全国信息素养大赛C赛道的一套高质量模拟题题面包装得像一个塔防小游戏矩形领地上散布着白蚁巢穴你只能在开战前布置防御炮台白蚁群按秒向四个方向蔓延问最少需要多长时间才能把蚁群完全清空。很多学生看到这个题的第一反应是“这要写个搜索吧”然后就开始硬模拟最后提交上去要么超时要么结果差一点。实际这道题真正考的是图遍历、队列、二分答案和边界控制这些C基本功题目把算法藏在了一个故事下面。这篇文章就把我当时备赛的完整拆解过程写出来从题目建模、算法选型、代码实现到常见坑点都有想备战信息素养大赛或者准备蓝桥杯、CSP这类竞赛的同学都拿它当个参考。1. 题目复盘这道题到底在考什么1.1 先还原一下题面模型竞赛题虽然没有完全公开的标准题面但从备赛训练中的版本来看“战胜白蚁”的模型大概是这样的给你一张n * m的地图地图上有若干个白蚁巢穴作为扩散起点每秒白蚁会向上、下、左、右四个相邻格子扩散一格。你可以在开战前选定一些格子布置防御炮台每个炮台有固定的攻击半径开战后会持续清剿进入攻击范围内的白蚁。题目要求的是在所有炮台位置确定的前提下能够把全部白蚁清剿干净的最短时间是多少。这道题本质上是一个“带防御设施的感染扩散模拟”。把白蚁群想象成火灾蔓延炮台是消防队你要算的是火多久能被扑灭。有了这个具象化的理解之后题目就不再是“打游戏”而是一个可以用算法精确计算的离线决策问题。1.2 它为什么是信息素养大赛的“压轴脸”全国信息素养大赛C赛道的题目设置跟纯粹的ACM竞赛有一点不同它很看重把实际问题转化成代码的能力而不是只比谁数据结构背得熟。“战胜白蚁”恰恰就把二维网格、多源扩散、最优化时间这三个要素全部装进了一个看似游戏化的外壳里。这种题目对选手有两个要求一是能看穿包装识别出“扩散”对应BFS“最少时间”对应二分答案二是有扎实的C基本功能在规定时间内把模型写成不崩、不超时的代码。很多人在考场上一看题面很长心里就开始发怵实际上只要你把题干里的动作拆成“扩散”和“攻击”两类思路一下就清楚了。1.3 审题时最容易踩的误区我帮学生复盘的时候发现半数以上的人第一步就理解偏了。他们以为炮台是开战后可以移动或临时补建的于是写了一个类似实时策略游戏的循环每秒钟先判断哪里要被围攻然后把炮台挪过去。这其实是把一道离线最优化问题做成了在线贪心题目里明确规定“开战前布置”后续不能调整。另一类误区是混淆攻击半径炮台攻击范围是欧几里得距离还是曼哈顿距离这个必须看题面给的定义。很多学生默认按格子周围一圈计算把r2理解成十字范围结果样例能过大数据全挂。这就是典型的没把规则写进代码模型里而是一开始就在脑子里面脑补规则。2. 算法选型与建模为什么绕不开BFS和二分2.1 把地图抽象成状态集合处理这类问题的第一步是把地图变成程序能懂的二维网格。我习惯用一个vectorvectorchar存原始地图其中.表示空地#表示障碍物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)次比如maxT100000时只需要17次左右整体复杂度大约O(n*m*log(maxT))稳得很。3. 核心代码实现C关键语法逐个敲一遍3.1 二维数组、字符串数组和结构体初始化很多初学者写这道题第一段代码还没开始写搜索就先被初始化绊倒了。二维数组如果你确定最大尺寸可以用char grid[1005][1005];这种静态数组但最好用memset初始化否则上一组测试数据的残留值会影响判断。如果你更喜欢动态分配就用vectorvectorvectorchar grid(n, vectorchar(m, .));这行代码的含义是创建一个n行、每行有m个字符的二维vector每个元素初始化为.。这里有一个容易忽略的点vectorvectorchar两个之间在旧标准里需要空格写成 否则部分编译器可能解析成右移运算符。虽然现代C11已经修复了这个问题但比赛环境如果用的编译器比较老建议还是空格隔开省得编译报错时一脸懵。字符串数组初始化同样有很多坑。用字符数组存字符串时记得要给结尾的\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(vectorpairint,int starts, int limit) { queuepairint,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这样天然就起到了“是否访问过”的标记作用。队列里存pairint,int组合了横纵坐标简单直接。如果你用的是std::pair记得q.push({nx, ny});这种花括号初始化在C11之后才支持。部分老比赛环境可能不支持那就老老实实q.push(make_pair(nx, ny));。3.3 暴力BFS模拟版本先保证能算对拿到一道题第一版代码我永远建议先写一个逻辑最简单、能跑出正确结果的版本哪怕它慢。这样你可以拿它和后面的优化版对拍。暴力版本的思路是每秒钟让所有存活的白蚁向四周扩展同时统计炮台射程内还有没有白蚁。当某一次扩散后所有白蚁都在炮台攻击范围内且没有新增扩散目标就认为清剿完成。int simulate(vectorpairint,int starts, vectorpairint,int towers, int r) { queueNode 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, vectorpairint,int starts, vectorpairint,int towers, int r) { queuepairint,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)这些函数在C11里都有比赛环境一般支持。还有一个容易被忽略的“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_ptrchar[]管理动态字符数组能省去手动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界面简单适合新手但它的默认编译器版本通常很老对一些新标准支持不够好用的时候把编译器设置改成C14或C17。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竞赛里少踩几个坑多拿一点分。
