3669 Meteor Shower

問題概要

座標平面上の格子点にM個の隕石が降ってくる。
それぞれの隕石の座標(xi,yi)および時間tiが与えられる。

マスに隕石が落ちると、それ以降、そのマスおよび接する4マスに立ち入ることはできなくなる。
最初Bessieは(0,0)にいて、第一象限を、時間1ごとに座標軸に平行に1だけ動けるとき、
Bessieが安全な場所まで移動するのにかかる最短時間を求めよ。
不可能な場合は-1を出力せよ。

M≦50000,0≦xi,yi≦300,ti≦1000を満たす。

解法

各マスについて、最初に隕石が降ってくる時間を求めておく。
その後、座標平面の(0,0)から幅優先探索で安全な地点を探す。

ソースコード

const int n=305,dy[]={-1,0,1,0,0},dx[]={0,-1,0,1,0};
int m,safe[n][n];
bool v[n][n];

int main()
{
	scanf("%d",&m);
	rep(i,n)rep(j,n)safe[i][j]=inf;
	rep(i,m)
	{
		int x,y,t; scanf("%d%d%d",&x,&y,&t);
		rep(d,5)
		{
			int ny=y+dy[d],nx=x+dx[d];
			if(0<=ny&&ny<n&&0<=nx&&nx<n)safe[ny][nx]=min(safe[ny][nx],t);
		}
	}
	queue<pair<int,pi> > Q; Q.push(mp(0,mp(0,0)));
	while(!Q.empty())
	{
		int y=Q.front().second.first,x=Q.front().second.second;
		int c=Q.front().first; Q.pop();
		if(v[y][x])continue;
		v[y][x]=1;
		if(safe[y][x]==inf)
		{
			printf("%d\n",c); return 0;
		}
		rep(d,4)
		{
			int ny=y+dy[d],nx=x+dx[d];
			if(0<=ny&&ny<n&&0<=nx&&nx<n&&!v[ny][nx]&&c+1<safe[ny][nx])
			Q.push(mp(c+1,mp(ny,nx)));
		}
	}
	puts("-1");
	return 0;
}