记录编号	7862	评测结果	AAAAAAAAAA
题目名称	[BYVoid S1] 血色叛徒	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.641 s
提交时间	2008-11-11 21:53:01	内存使用	4.23 MiB

#include <iostream>
#include <fstream>

#define MAXN 510
#define INF 99999999

using namespace std;

const int Dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m,a,b,ans[MAXN][MAXN],visit[MAXN][MAXN],que[MAXN*MAXN+500][2];

void run()
{
	int head=-1,tail=a-1,x,y,a,b,d;
	while (head<tail)
	{
		head++;
		x=que[head][0];
		y=que[head][1];
		for (d=0;d<4;d++)
		{
			a=x+Dir[d][0];
			b=y+Dir[d][1];
			if (a>=0 && a<=n && b>=0 &&b<=m && visit[a][b]==0)
			{
				visit[a][b]=1;
				ans[a][b]=ans[x][y]+1;
				tail++;
				que[tail][0]=a;
				que[tail][1]=b;
			}
		}
	}
}

void ini()
{
	int i,j,x,y;
	for (i=0;i<MAXN;i++)
		for (j=0;j<MAXN;j++)
			ans[i][j]=INF;
	cin>>n>>m>>a>>b;
	for (i=1;i<=a;i++)
	{
		scanf("%d%d",&x,&y);
		ans[x][y]=0;
		visit[x][y]=1;
		que[i-1][0]=x;
		que[i-1][1]=y;
	}
	run();
	for (i=1;i<=b;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%d",ans[x][y]);
		if (i!=b)
			printf("\n");
	}
	
}

int main()
{
	freopen("crusade.in","r",stdin);
	freopen("crusade.out","w",stdout);
	ini();
	return 0;
}