COGS 138. [USACO Feb08] 流星雨

借这道题来回忆一下广度优先搜索（BFS）
一开始的时候乱写成dfs了(逃..

bfs就是类似对树进行一层一层的遍历，具体做法就是开一个队列，每次从队头取出节点，对他所连通的节点进行遍历，如果是未遍历过的节点就加入队列，直到队列为空时遍历完成。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n;
int a[400][400],viss[400][400];
int visx[5]={1,-1,0,0,0};
int visy[5]={0,0,1,-1,0};

struct node{
	int x,y,t;	
};
int okk(int x,int y,int t){
	if(x>=0&&y>=0&&!viss[x][y]) {
		if(a[x][y]==-1) return 1;
		else if(a[x][y]>t) return 1;
	}
	return 0;	
}

void bfs(){
	queue<node> q;
	q.push((node){0,0,0}); 
	while(!q.empty()){
		node ppp=q.front();q.pop();
		if(a[ppp.x][ppp.y]==-1){
			printf("%d",ppp.t);
			return ;	
		}
		for(int i=0;i<4;i++){	
			if(okk(ppp.x+visx[i],ppp.y+visy[i],ppp.t+1)){
				q.push((node){ppp.x+visx[i],ppp.y+visy[i],ppp.t+1});
				viss[ppp.x+visx[i]][ppp.y+visy[i]]=1;
			}
		}
	}
	printf("-1");
	return ;
}

void chuli(int x,int y,int t){
	for(int i=0;i<5;i++){
		if(x+visx[i]>=0&&y+visy[i]>=0){ 
			if(a[x+visx[i]][y+visy[i]]==-1)
				a[x+visx[i]][y+visy[i]]=t;
			else a[x+visx[i]][y+visy[i]]=min(a[x+visx[i]][y+visy[i]],t);	
		}	
	}
	return ;
}

int main(){
	freopen("meteor.in","r",stdin);
	freopen("meteor.out","w",stdout);
	memset(a,-1,sizeof(a));
	scanf("%d",&n);
	int x,y,t;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&t);
		chuli(x,y,t);
	}
	bfs();
	return 0;
}