【题解】 P1332 血色先锋队

今天%你赛又被吊打了很不爽所以写一篇唯一会的题的题解来开心一下TAT

题目的大意就是让我们从不同的起点开始向外拓展，然后最先拓展的点就用一个ans的二维数组存下来，因为luogu上面数据比较水，所以不建议大家用直接暴力算的方法（因为luogu数据比较水，所以暴力亲测还可以过，但最好是用搜索的方法

我们可以把初始感染源都放在队列里面，然后不断的向外拓展，直到head=tail的时候退出，二维数组ans记录答案，每次记录的就是当前的ans=之前的队列拓展点+1就好了，因为广搜是单调的所以不用考虑大小问题

上代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

int ans[1001][1001],queue[1000001][2],head,tail,n,k1,k2,m;
bool vis[1001][1001];
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};

int main()
{
	memset(ans,127/3,sizeof(ans));
	scanf("%d%d%d%d",&n,&m,&k1,&k2);
	for(int i=1; i<=k1; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		queue[++tail][0]=x; queue[tail][1]=y;
		ans[x][y]=0; vis[x][y]=1;
	}
	while(head<tail)
	{
		head++;
		for(int i=0; i<4; i++)
		{
			int sx=queue[head][0]+xx[i],sy=queue[head][1]+yy[i];
			if(sx>0 && sy>0 && sx<=n && sy<=m && !vis[sx][sy])
			{
				vis[sx][sy]=1;
				queue[++tail][0]=sx; 
				queue[tail][1]=sy;
				ans[sx][sy]=ans[queue[head][0]][queue[head][1]]+1;
			}
		}
	}
	for(int i=1; i<=k2; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",ans[x][y]);
	}
}