血色先锋军（多源 BFS）题解复盘
基本信息
| 项目 | 内容 |
|---|
| 题目编号、来源 | 血色先锋军 |
| 训练层级 | B BFS进阶 |
| 知识版块 | BFS、多源 BFS、网格搜索 |
解题前・关键信号识别
| 维度 | 分析 |
|---|
| 目标、约束、底层结构 | 目标：给定多个感染源，求每个领主被感染的最短时间；约束：n,m ≤ 500，a,b ≤ 1e5；底层结构：多个起点同时扩散，每个格子被第一次到达的时间即为感染时间。 |
| 数据规模 | n×m ≤ 250000，BFS 完全可行。 |
| 候选算法和依据 | 多源 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. 坐标边界判断写错（nx<=0而非nx<0）；4. 读取领主时没有单独存储，导致输出顺序错误。 |
| 边界和易错点 | 1. 起点（感染源）的感染时间为 0；2. 入队时立即标记vis，防止重复入队；3. 输出顺序必须与输入顺序一致，所以需要先存储所有领主；4. 坐标从 1 开始，边界判断为nx<1 || nx>n || ny<1 || ny>m。 |
| 下次看到什么信号，我应该想到这个方法 | 看到「多个起点 + 同时扩散 + 求最短时间/距离」，用多源 BFS。 |
AC 完整代码
#include<iostream>#include<cstring>#include<queue>#include<algorithm>#include<set>#include<vector>usingnamespacestd;intv[505][505];intvis[505][505];set<pair<int,int>>s1;vector<pair<int,int>>s2;intdx[]={-1,0,1,0};intdy[]={0,1,0,-1};intn,m,a,b;voidbfs(){queue<pair<int,int>>q;for(auto&s:s1){intx=s.first;inty=s.second;q.push({x,y});vis[x][y]=1;}while(!q.empty()){auto[x,y]=q.front();q.pop();for(inti=0;i<4;i++){intnx=x+dx[i];intny=y+dy[i];if(nx<=0||nx>n||ny<=0||ny>m)continue;if(vis[nx][ny]==0){v[nx][ny]=v[x][y]+1;q.push({nx,ny});vis[nx][ny]=1;}}}}intmain(){cin>>n>>m>>a>>b;for(inti=0;i<a;i++){intx,y;cin>>x>>y;s1.insert({x,y});}for(inti=0;i<b;i++){intx,y;cin>>x>>y;s2.push_back({x,y});}bfs();for(auto&s:s2){intx=s.first;inty=s.second;cout<<v[x][y]<<endl;}return0;}
