luogu P1332 血色先锋队[bfs]
2024-09-05 12:24:08
题目描述
巫妖王的天灾军团终于卷土重来,血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团,以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围,现在他们将主力只好聚集了起来,以抵抗天灾军团的围剿。可怕的是,他们之中有人感染上了亡灵瘟疫,如果不设法阻止瘟疫的扩散,很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒,这个叛徒已经投靠了天灾军团,想要将整个血色先锋军全部转化为天灾军团!无需惊讶,你就是那个叛徒。在你的行踪败露之前,要尽快完成巫妖王交给你的任务。
军团是一个N行M列的矩阵,每个单元是一个血色先锋军的成员。感染瘟疫的人,每过一个小时,就会向四周扩散瘟疫,直到所有人全部感染上瘟疫。你已经掌握了感染源的位置,任务是算出血色先锋军的领主们感染瘟疫的时间,并且将它报告给巫妖王,以便对血色先锋军进行一轮有针对性的围剿。
输入输出格式
输入格式:
第1行:四个整数N,M,A,B,表示军团矩阵有N行M列。有A个感染源,B为血色敢死队中领主的数量。
接下来A行:每行有两个整数x,y,表示感染源在第x行第y列。
接下来B行:每行有两个整数x,y,表示领主的位置在第x行第y列。
【数据规模】
1<=M,N<=500
1<=A,B<=M*N
输出格式:
第1至B行:每行一个整数,表示这个领主感染瘟疫的时间,输出顺序与输入顺序一致。如果某个人的位置在感染源,那么他感染瘟疫的时间为0。
输入输出样例
输入样例#1:
5 4 2 3
1 1
5 4
3 3
5 3
2 4
输出样例#1:
3
1
3
说明
如下图,标记出了所有人感染瘟疫的时间以及感染源和领主的位置。
发现年段布置的水题没有做啊。。。于是花10分钟水一下。。。
可是,由于没有发现领主们跟感染源站在一起(还有这么傻的?),对对对,我没有1A
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std; typedef pair<int,int> PII; struct node{
int x,y,dep;
node(int x=,int y=,int dep=):
x(x),y(y),dep(dep){}
}; const int maxn=; int n,m,n1,n2,get=;
int site[maxn][maxn],vis[maxn][maxn];
int ans[maxn*maxn];
int dx[]={,-,,},dy[]={-,,,};
queue<node> que; void init(){
scanf("%d%d%d%d",&n,&m,&n1,&n2);
for(int i=,x,y;i<=n1;i++){
scanf("%d%d",&x,&y);
vis[x][y]=;
que.push(node(x,y,));
}
for(int i=,x,y;i<=n2;i++){
scanf("%d%d",&x,&y);
if(vis[x][y]) get++;
site[x][y]=i;
}
} void bfs(){
while(){
node pos=que.front(); que.pop();
int posx=pos.x,posy=pos.y,posdep=pos.dep;
for(int i=;i<;i++){
int nxtx=posx+dx[i],nxty=posy+dy[i];
if(nxtx>=&&nxtx<=n&&nxty>=&&nxty<=m)
if(!vis[nxtx][nxty]){
vis[nxtx][nxty]=;
que.push(node(nxtx,nxty,posdep+));
if(site[nxtx][nxty]){
ans[site[nxtx][nxty]]=posdep+;
if(++get==n2) return;
}
}
}
}
} int main(){
init();
bfs();
for(int i=;i<=n2;i++)
printf("%d\n",ans[i]);
return ;
}
最新文章
- PPTP-VPN第一章——部署与简单使用
- HFS汉化版|简易HTTP服务器
- Java Java Java
- 配置Linux任务计划
- 亲测 logminer挖掘
- Python—开始编程
- AutoLayout适配
- 功能:使用QQ号登陆,并加上微信和短信提醒,是否增量备份可选,阿里大鱼短信发送开发与测试,聚合数据(用JSON发短信,比较清楚)
- OpenSSl 加密解密 示例(终于有编程实践了)
- RHEL4-Partition Image系统备份(软件版)
- [Swust OJ 797]--Palindromic Squares(回文数水题)
- 编程语言性能游戏排行榜,C/C++第一ATS第二JAVA第三
- JS页面跳转的常用方法整理.
- 系统性能监测(使用nmon、nmonanalyser)
- python 玩耍天地
- LODOP中预览界面查看打印机的可打区域具体值
- 对世界首款“人工智能”ERP系统HUE的初步了解 - AI ERP - WAP - 万革始
- [蓝桥杯]ALGO-79.算法训练_删除数组零元素
- 从Unauthorized 401错误学习Spring Boot的Actuator
- np.repeat函数