poj 3669 Meteor Shower

预处理地图，表示当前点爆炸的最早时间，然后bfs找到安全区域。

坑点：1.有可能一开始的0,0点就被炸了

2.安全区域不是0-300,0-300，而是0-正无穷,0-正无穷，所以边界判断只要x>=0&&y>=0就够了。

其他的没什么

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; int maps[305][305]; //bool vis[305][305][1005]; int dx[]={0,0,-1,1,0}; int dy[]={-1,1,0,0,0}; struct node { int x,y; int t; }v[50005]; int top; int n; int times; int vis[305][305]; bool cmp(node a,node b) { return a.t
      
       =0&&/*x<=300&&*/y>=0/*&&y<=300*/; } void bfs() { queue
       
         Q; node t,f; t.x=0;t.y=0;t.t=0; memset(vis,0,sizeof(vis)); Q.push(t); while(!Q.empty()) { t=Q.front();Q.pop(); for(int d=0;d<4;d++) { f=t; f.x+=dx[d]; f.y+=dy[d]; f.t++; if(isok(f.x,f.y)&&maps[f.x][f.y]>f.t&&!vis[f.x][f.y]) { vis[f.x][f.y]=1; if(maps[f.x][f.y]>times) { printf("%d\n",f.t); return; } Q.push(f); } } } printf("-1\n"); } int main() { while(~scanf("%d",&n)) { memset(maps,0x3f,sizeof(maps)); top=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&v[top].x,&v[top].y,&v[top].t); top++; } sort(v,v+top,cmp); for(int i=0;i