记录编号	516800	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	pztl	是否通过	通过
代码语言	C++	运行时间	0.062 s
提交时间	2018-10-26 11:41:22	内存使用	5.17 MiB

#include <cstring>
#include <cstdio>
#define N 505
int f[N<<1][5],l=0,r=0,m,G[N<<1][N<<1],fx[5]={0,0,-1,1},fy[5]={1,-1,0,0};
bool vis[N<<1][N<<1];
inline int min(int a,int b) {return a>b?b:a;}
void init(int x,int y,int t)
{
    G[x][y]=G[x][y]==-1?t:min(G[x][y],t);
    for(int i=0;i<4;++i)
    {
        int tx=x+fx[i],ty=y+fy[i];
        if(tx>=0&&ty>=0) G[tx][ty]=G[tx][ty]==-1?t:min(G[tx][ty],t);
    }
}
int main()
{
	freopen("meteor.in","r",stdin);
	freopen("meteor.out","w",stdout);
    scanf("%d",&m);
    memset(G,-1,sizeof(G));
    for(int x,y,t,i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&t);
        init(x,y,t);
    }
    f[++r][1]=0;
    f[r][2]=0;
    vis[0][0]=1;
    for(;l<r;)
    {
        int nowx=f[++l][1],nowy=f[l][2];
        for(int i=0;i<4;++i)
        {
            int tx=nowx+fx[i],ty=nowy+fy[i];
            if(G[tx][ty]==-1&&tx>=0&&ty>=0)
            {
                printf("%d\n",f[l][3]+1);
                return 0;
            }
            if(tx>=0&&ty>=0&&!vis[tx][ty]&&G[tx][ty]>f[l][3]+1)
            {
                vis[tx][ty]=1;
                f[++r][1]=tx;
                f[r][2]=ty;
                f[r][3]=f[l][3]+1;
            }
        }
    }
    printf("-1\n");
    return 0;
}