题意：
给定几个坐标，在这些坐标上 t 时刻会有陨石雨。
怎样在最短的时间内找到一个安全的地方。
方法：预处理，把每个坐标有陨石的地方预处理出来，这样在bfs的时候会很简单，比如不用考虑待在原点不懂，或者往回走之类的
View Code
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<math.h> 4 #include<queue> 5 #include<algorithm> 6 using namespace std; 7 const int maxn = 405; 8 const int inf=9999999; 9 int map[ maxn ][ maxn ]; 10 const int dx[]={0,0,0,1,-1}; 11 const int dy[]={0,1,-1,0,0}; 12 13 struct Node{ 14 int x,y,time; 15 }; 16 int bfs(){ 17 if( map[ 0 ][ 0 ]==0 ) return -1; 18 else if( map[ 0 ][ 0 ]==-1 ) return 0; 19 Node tmp,now; 20 tmp.x=tmp.y=tmp.time=0; 21 queue<Node>q; 22 q.push( tmp ); 23 while( !q.empty() ){ 24 now=q.front(); 25 q.pop(); 26 for( int i=1;i<5;i++ ){ 27 tmp.x=now.x+dx[ i ]; 28 tmp.y=now.y+dy[ i ]; 29 tmp.time=now.time+1; 30 if( tmp.x<0||tmp.y<0||tmp.x>=maxn||tmp.y>=maxn ) continue; 31 if( map[ tmp.x ][ tmp.y ]==-1 ) return tmp.time; 32 if( tmp.time>=map[ tmp.x ][ tmp.y ] ) continue; 33 map[ tmp.x ][ tmp.y ]=tmp.time; 34 q.push( tmp ); 35 } 36 } 37 return -1; 38 } 39 40 int main(){ 41 int n; 42 while( scanf("%d",&n)!=EOF ){ 43 int x,y,t; 44 memset( map,-1,sizeof(map) ); 45 while( n-- ){ 46 scanf("%d%d%d",&x,&y,&t); 47 for( int k=0;k<5;k++ ){ 48 int tx=x+dx[ k ]; 49 int ty=y+dy[ k ]; 50 if( tx<0||ty<0||tx>=maxn||ty>=maxn ) continue; 51 if( map[ tx ][ ty ]==-1 ) map[ tx ][ ty ]=t; 52 else map[ tx ][ ty ]=min( map[ tx ][ ty ],t ); 53 } 54 } 55 printf("%d\n",bfs()); 56 } 57 return 0; 58 }