題目背景

巫妖王的天災軍團終于卷土重來，血色十字軍組織了一支先鋒軍前往諾森德大陸對抗天災軍團，以及一切沾有亡靈氣息的生物。孤立于聯盟和部落的血色先鋒軍很快就遭到了天災軍團的重重包圍，現在他們將主力只好聚集了起來，以抵抗天災軍團的圍剿。可怕的是，他們之中有人感染上了亡靈瘟疫，如果不設法阻止瘟疫的擴散，很快就會遭到滅頂之災。大領主阿比迪斯已經開始調查瘟疫的源頭。原來是血色先鋒軍的內部出現了叛徒，這個叛徒已經投靠了天災軍團，想要將整個血色先鋒軍全部轉化為天災軍團！無需驚訝，你就是那個叛徒。在你的行蹤敗露之前，要盡快完成巫妖王交給你的任務。

題目描述

軍團是一個?n?行?m?列的矩陣，每個單元是一個血色先鋒軍的成員。感染瘟疫的人，每過一個小時，就會向四周擴散瘟疫，直到所有人全部感染上瘟疫。你已經掌握了感染源的位置，任務是算出血色先鋒軍的領主們感染瘟疫的時間，并且將它報告給巫妖王，以便對血色先鋒軍進行一輪有針對性的圍剿。

輸入格式

第?1?行：四個整數?n，m，a，b，表示軍團矩陣有?n?行?m?列。有?a?個感染源，b?為血色敢死隊中領主的數量。

接下來?a?行：每行有兩個整數?x，y，表示感染源在第?x?行第?y?列。

接下來?b?行：每行有兩個整數?x，y，表示領主的位置在第?x?行第?y?列。

輸出格式

第?1?至?b?行：每行一個整數，表示這個領主感染瘟疫的時間，輸出順序與輸入順序一致。如果某個人的位置在感染源，那么他感染瘟疫的時間為?0。

輸入輸出樣例

輸入 #1復制

5 4 2 3
1 1
5 4
3 3
5 3
2 4

輸出 #1復制

3
1
3

說明/提示

輸入輸出樣例 1 解釋

如下圖，標記出了所有人感染瘟疫的時間以及感染源和領主的位置。

數據規模與約定

對于?100%?的數據，保證?1≤n,m≤500，1≤a,b≤10^5。

題目鏈接：P1332 血色先鋒隊 - 洛谷

學習鏈接：BFS習題課(上) | 從此搞懂搜索題的套路! | 入門必看_嗶哩嗶哩_bilibili

代碼如下：?

#include<bits/stdc++.h>
using namespace std;
int n,m;//矩陣規模
int a;//感染源數量
int b;//領主數量
typedef pair<int,int> PII;//坐標
queue<PII> q;//坐標隊列
int dist[505][505];//距離數組
int dx[4]={-1,0,1,0};//x方向偏移量
int dy[4]={0,1,0,-1};//y方向偏移量int main()
{cin>>n>>m>>a>>b;//初始化dist數組memset(dist,-1,sizeof(dist));//將a個感染源入隊 int x,y;while(a--){//輸入感染源坐標 cin>>x>>y;//將感染源入隊q.push({x,y});//記錄距離dist[x][y]=0; } //當隊列不為空時while(!q.empty()) {//取隊頭坐標PII t=q.front();//彈出q.pop();//遍歷感染的四個方向for(int i=0;i<4;i++){//被感染的坐標int nx=t.first+dx[i];int ny=t.second+dy[i];//如果越界,跳過該方向坐標 if(nx<1 || nx>n || ny<1 || ny>m)	continue;//如果被感染過if(dist[nx][ny]!=-1)	continue;//若經過了重重考驗//入隊q.push({nx,ny});//記錄距離dist[nx][ny]=dist[t.first][t.second]+1;	} }//輸出領主被感染的時間while(b--){cin>>x>>y;cout<<dist[x][y]<<endl;} return 0;
} 

?