记录编号	31612	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.094 s
提交时间	2011-11-03 11:26:24	内存使用	2.14 MiB

#include <cstdio>
#include <cstdlib>
using namespace std;

const int RUL[5][2]={{0,-1},{0,1},{-1,0},{1,0},{0,0}};
int x[50001],y[50001],t[50001],quex[91204]={0},quey[91204]={0},tim[91204]={0};
bool used[302][302]={{true}},des[302][302]={{false}},dan[302][302]={{false}};

void swap(int &x,int &y)
{
	int temp;
	temp=x;
	x=y;
	y=temp;
}

void qqsort(int l,int r)
{
	int ll,rr,temp;
	ll=l;
	rr=r;
	temp=t[rand()%(r-l+1)+l];
	while (ll<=rr)
	{
		while (t[ll]<temp)
			ll++;
		while (temp<t[rr])
			rr--;
		if (ll<=rr)
		{
			swap(t[ll],t[rr]);
			swap(x[ll],x[rr]);
			swap(y[ll],y[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(l,rr);
	if (ll<r)
		qqsort(ll,r);
}

int main(void)
{
	freopen("meteor.in","r",stdin);
	freopen("meteor.out","w",stdout);
	int i,j,m,xt,yt,num=0,tail=0,head=0;
	scanf("%d\n",&m);
	for (i=0;i<m;i++)
	{
		scanf("%d %d %d\n",&x[i],&y[i],&t[i]);
		for (j=0;j<=4;j++)
		{
			xt=x[i]+RUL[j][0];
			yt=y[i]+RUL[j][1];
			if (xt>=0&&yt>=0&&xt<=301&&yt<=301)
				dan[xt][yt]=true;
		}
	}
	if (dan[0][0]=false)
	{
		printf("0\n");
		fclose(stdin);
		fclose(stdout);
		return(0);
	}
	qqsort(0,m-1);
	t[m]=2000000000;
	while (0==t[num])
	{
		for (i=0;i<=4;i++)
		{
			xt=x[num]+RUL[i][0];
			yt=y[num]+RUL[i][1];
			if (xt>=0&&yt>=0&&xt<=301&&yt<=301)
				des[xt][yt]=true;
		}
		num++;
	}
	if (des[0][0])
		tail=1;
	while (tail<=head)
	{
		while (tim[tail]+1==t[num])
		{
			for (i=0;i<=4;i++)
			{
				xt=x[num]+RUL[i][0];
				yt=y[num]+RUL[i][1];
				if (xt>=0&&yt>=0&&xt<=301&&yt<=301)
					des[xt][yt]=true;
			}
			num++;
		}
		for (i=0;i<=3;i++)
		{
			xt=quex[tail]+RUL[i][0];
			yt=quey[tail]+RUL[i][1];
			if (xt>=0&&yt>=0&&xt<=301&&yt<=301&&!des[xt][yt]&&!used[xt][yt])
			{
				head++;
				quex[head]=xt;
				quey[head]=yt;
				tim[head]=tim[tail]+1;
				used[xt][yt]=true;
				if (!dan[xt][yt])
				{
					printf("%d\n",tim[head]);
					fclose(stdin);
					fclose(stdout);
					return(0);
				}
			}
		}
		tail++;
	}
	printf("-1\n");
	fclose(stdin);
	fclose(stdout);
	return(0);
}