poj3669 Meteor Shower(BFS)

题目链接:poj3669 Meteor Shower

我只想说这题WA了后去看讨论才发现的坑点，除了要注意原点外，流星范围题目给的是[0,300]，到302的位置就绝对安全了。。。

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #include<cstring>

 #include<algorithm>

 #define CLR(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 const int N = ;

 const int inf = 0x3f3f3f3f;

 int dir[][]={-,,,,,,,-};

 int vis[N][N], g[N][N];

 struct point{

     int x, y;

     int d;

     point(int x=,int y=,int d=):x(x),y(y),d(d){}

 };

 int jud(int x, int y, int d){

     if(x >= && x < N && y >=  && y < N && !vis[x][y] && d < g[x][y])

         return ;

     return ;

 }

 int bfs(){

     CLR(vis, );

     queue<point>q;

     point u, v;

     vis[][] = ;

     q.push(point(,,));

     while(!q.empty()){

         u = q.front(); q.pop();

         for(int i = ; i < ; ++i){

             v.x = u.x + dir[i][];

             v.y = u.y + dir[i][];

             v.d = u.d + ;

             if(jud(v.x, v.y, v.d)){

                 if(g[v.x][v.y] == inf)//安全区域

                     return v.d;

                 vis[v.x][v.y] = ;

                 q.push(v);

             }

         }

     }

     return -;

 }

 int main(){

     int m, i, x, y, t;

     CLR(g,inf);

     scanf("%d", &m);

     for(i = ; i < m; ++i){

         scanf("%d%d%d", &x, &y, &t);

         g[x][y] = min(t, g[x][y]);

         if(x >  && t < g[x-][y])

             g[x-][y] = t;

         if(y >  && t < g[x][y-])

             g[x][y-] = t;

         g[x+][y] = min(t, g[x+][y]);

         g[x][y+] = min(t, g[x][y+]);

     }

     if(g[][] == ){printf("-1\n");return ;}

     if(g[][] == inf){printf("0\n");return ;}

     printf("%d\n",bfs());

     return ;

 }