全WA求助
查看原帖
全WA求助
572482
Dream_weavers楼主2022/5/7 10:30

很明显的bfs,但就是调不好,样例也没过

我是不是要AFO了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
const int M=1e6+5;

int py[4][2]={1,0,0,1,-1,0,0,-1};
int n,m,a,b,top;
int mp[N][N],vis[N][N];
int q[M][2];

void bfs(){
	int x,y;
	int h=0,t=top;
	while(h<t){
		h++;
		x=q[h][0],y=q[h][1];
		vis[x][y]=1;
		for(int i=0;i<4;i++){
			int dx=x+py[i][0];
			int dy=y+py[i][1];
			if(dx<1||dy<1||dx>n||dy>m||vis[dx][dy])continue;
			vis[dx][dy]=1;
			mp[dx][dy]=mp[x][y]+1;
			t++;
			q[t][0]=dx,q[t][1]=dy;
		}
	}
}

signed main(){
	int x,y;
	scanf("%lld%lld%lld%lld",&n,&m,&a,&b);
	while(a--){
		scanf("%lld%lld",&x,&y);
		mp[x][y]=1,top++;
		q[top][0]=x,q[top][1]=y;
	}
	bfs();
	while(b--){
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",mp[x][y]);
	} 
	return 0;
}

2022/5/7 10:30
加载中...