血色先锋军多源 BFS题解复盘基本信息项目内容题目编号、来源血色先锋军训练层级B BFS进阶知识版块BFS、多源 BFS、网格搜索解题前・关键信号识别维度分析目标、约束、底层结构目标给定多个感染源求每个领主被感染的最短时间约束n,m ≤ 500a,b ≤ 1e5底层结构多个起点同时扩散每个格子被第一次到达的时间即为感染时间。数据规模n×m ≤ 250000BFS 完全可行。候选算法和依据多源 BFS依据多个感染源同时向四周扩散每个格子被最早到达的时间就是感染时间。复杂度预判时间复杂度 O(n×m)空间复杂度 O(n×m)。解题后・外化复盘维度内容实现结构 / 核心思路第一步将所有感染源坐标存入队列标记vis[x][y]1感染时间v[x][y]0第二步从队列中取出点枚举 4 个方向第三步若邻居未访问vis[nx][ny]0则v[nx][ny]v[x][y]1标记访问并入队第四步最后按输入顺序输出每个领主的v[x][y]。核心思想多源 BFS 从所有起点同时出发第一次到达即为最短时间天然模拟“瘟疫扩散”过程。错因回溯1. 用单源 BFS 对每个领主分别搜索导致超时2. 忘记标记vis导致重复入队3. 坐标边界判断写错nx0而非nx04. 读取领主时没有单独存储导致输出顺序错误。边界和易错点1. 起点感染源的感染时间为 02. 入队时立即标记vis防止重复入队3. 输出顺序必须与输入顺序一致所以需要先存储所有领主4. 坐标从 1 开始边界判断为nx1 || nxn || ny1 || nym。下次看到什么信号我应该想到这个方法看到「多个起点 同时扩散 求最短时间/距离」用多源 BFS。AC 完整代码#includeiostream#includecstring#includequeue#includealgorithm#includeset#includevectorusingnamespacestd;intv[505][505];intvis[505][505];setpairint,ints1;vectorpairint,ints2;intdx[]{-1,0,1,0};intdy[]{0,1,0,-1};intn,m,a,b;voidbfs(){queuepairint,intq;for(autos:s1){intxs.first;intys.second;q.push({x,y});vis[x][y]1;}while(!q.empty()){auto[x,y]q.front();q.pop();for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(nx0||nxn||ny0||nym)continue;if(vis[nx][ny]0){v[nx][ny]v[x][y]1;q.push({nx,ny});vis[nx][ny]1;}}}}intmain(){cinnmab;for(inti0;ia;i){intx,y;cinxy;s1.insert({x,y});}for(inti0;ib;i){intx,y;cinxy;s2.push_back({x,y});}bfs();for(autos:s2){intxs.first;intys.second;coutv[x][y]endl;}return0;}