记录编号	553799	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	城南花已开	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2020-08-25 23:42:04	内存使用	1.30 MiB

# include <iostream>
# include <cstdio>
using namespace std;
int m,a,b,c,farm1[303][303],qx[90005],qy[90005],time1[900005],sign=-1,heng[5]={0,1,-1,0,0},shu[5]={0,0,0,1,-1};
bool farm2[303][303];
void bfs(){
	int head=0,tail=1,i;
	qx[1]=0;
	qy[1]=0;
	time1[1]=0;
	farm2[0][0]=false;
	do{
		head++;
		for(int i=1;i<=4;i++){
			if(qx[head]+heng[i]>=0&&qy[head]+shu[i]>=0){
				if(time1[head]+1<farm1[qx[head]+heng[i]][qy[head]+shu[i]]&&farm2[qx[head]+heng[i]][qy[head]+shu[i]]==true){
				    tail++;
				    qx[tail]=qx[head]+heng[i];
				    qy[tail]=qy[head]+shu[i];
				    time1[tail]=time1[head]+1;
				    farm2[qx[tail]][qy[tail]]=false;
				    if(farm1[qx[tail]][qy[tail]]==50001){
				    	sign=0;
				    	printf("%d",time1[tail]);
				    	head=tail;
				    	break;
					}
				}
			}
		}
	}while(head<tail);
}
int main(){
	freopen("meteor.in","r",stdin);
	freopen("meteor.out","w",stdout);
	scanf("%d",&m);
	for(int i=0;i<303;i++){
		for(int j=0;j<303;j++){
			farm1[i][j]=50001;
			farm2[i][j]=true;
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		if(farm1[a][b]>c){
		    farm1[a][b]=c;
		}		
		if(farm1[a+1][b]>c){
		    farm1[a+1][b]=c;
		}
		if(a-1>=0){
		    if(farm1[a-1][b]>c){
		        farm1[a-1][b]=c;
		    }
		}
		if(farm1[a][b+1]>c){
		    farm1[a][b+1]=c;
		}
		if(b-1>=0){
		    if(farm1[a][b-1]>c){
		        farm1[a][b-1]=c;
		    }
	    }
	}
	bfs();
	if(sign==-1){
		printf("%d",-1);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}