记录编号	293321	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	open the window	是否通过	通过
代码语言	C++	运行时间	0.108 s
提交时间	2016-08-10 14:29:57	内存使用	99.57 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
struct point
{
   int x,y,t;
}a[50001];
bool v[302][302],b[1001][302][302],z[302][302];
int dx[]={0,0,-1,1},
    dy[]={-1,1,0,0};
int m,xx,yy,t=0,w=1,l=1,r;
int h[1000001][3];
int cmp(const point &c,const point &d)
{
	return c.t<d.t;
}
int main()
{
	freopen("meteor.in","r",stdin);
	freopen("meteor.out","w",stdout);
	scanf("%d",&m);
	for (int i=1; i<=m; ++i) 
	{
	  scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
	  v[a[i].x][a[i].y]=true;
	  b[a[i].t][a[i].x][a[i].y]=true;
	  for (int j=0; j<4; ++j)
	  {
	  	 xx=a[i].x+dx[j];
	  	 yy=a[i].y+dy[j];
	  	 if (xx>=0 && xx<302 && yy>=0 && yy<302) 
		 {
		    v[xx][yy]=true;
		    b[a[i].t][xx][yy]=true;
		 }
	  }
    }
	sort(a+1,a+m+1,cmp);
	z[0][0]=true; v[0][0]=true;
	while (t<w)
	{
		t++;
		for (int i=0; i<4; ++i)
		{
			xx=h[t][1]+dx[i];
			yy=h[t][2]+dy[i];
			int l=h[t][0]+1;
			while (!b[l][xx][yy] && l>-1) l--;
			if (l==-1)
			if (xx>=0 && xx<302 && yy>=0 && yy<302 && !z[xx][yy])
			{
			   	z[xx][yy]=true;
			   	w++;
			   	h[w][1]=xx;
			   	h[w][2]=yy;
			   	h[w][0]=h[t][0]+1;
			   	if (!v[xx][yy])
			   	{
			   		printf("%d\n",h[w][0]);
			   		return 0;
				}
			}
		}
	}
	printf("-1\n");
}