P1332血色先锋队题解

2020-12-12 21:49:13


(一道很水的bfs模板题)

我们来分析一下题目,他既然是说求最短时间,那么宽搜必然,想对基本算法,代码就很容易实现了

不多说,上代码,注释在代码中

#include<bits/stdc++.h>
using namespace std;

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};//四个方向拓展
int n,m,a,b,ans[1000005];//定义一个存放答案的数组
int Map[505][505];//地图
bool vis[505][505];//标记访问
struct node{
    int x,y,time;//当前位置以及所需时间
};
queue<node>q;//造队列,宽搜套路
int main(){
    cin>>n>>m>>a>>b;
    for(int i=1;i<=a;i++){
        int zx,zy;
        cin>>zx>>zy;
        q.push(node{zx,zy,0});//存放每一个瘟疫源头
        vis[zx][zy]=true;
    }
    for(int i=1;i<=b;i++){
        int zx,zy;
        cin>>zx>>zy;
        Map[zx][zy]=i;//存放领主位置。由于题目中说按序输出,所以没有领主就是0,有领主顺序标记
    }
    while(!q.empty()){
        node t=q.front();
        q.pop();
        if(t.x!=0&&t.y!=0)
            ans[Map[t.x][t.y]]=t.time;//判断是否感染到领主,如果有,就在相应位置上标记时间
        for(int i=0;i<4;i++){
            int xx=t.x+dx[i];
            int yy=t.y+dy[i];//四个方向拓展
            if(t.x>0&&t.x<=n&&t.y>0&&t.y<=n&&!vis[xx][yy]){//判断是否越界、被访问过
           q.push(node{xx,yy,t.time+1});//记录新感染源
                vis[xx][yy]=true;//标记已被感染
            }
        }
    }
    for(int i=1;i<=b;i++)
        cout<<ans[i]<<endl;//按序输出所需的感染时间
    return 0;
}