首页 > 代码库 > poj3669 Meteor Shower(BFS)

poj3669 Meteor Shower(BFS)

题目链接:poj3669 Meteor Shower

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

技术分享
 1 #include<cstdio> 2 #include<cmath> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 #define CLR(a,b) memset((a),(b),sizeof((a))) 7 using namespace std; 8  9 const int N = 303;10 const int inf = 0x3f3f3f3f;11 int dir[][2]={-1,0,1,0,0,1,0,-1};12 int vis[N][N], g[N][N];13 struct point{14     int x, y;15     int d;16     point(int x=0,int y=0,int d=0):x(x),y(y),d(d){}17 };18 int jud(int x, int y, int d){19     if(x >=0 && x < N && y >= 0 && y < N && !vis[x][y] && d < g[x][y])20         return 1;21     return 0;22 }23 int bfs(){24     CLR(vis, 0);25     queue<point>q;26     point u, v;27     vis[0][0] = 0;28     q.push(point(0,0,0));29     while(!q.empty()){30         u = q.front(); q.pop();31         for(int i = 0; i < 4; ++i){32             v.x = u.x + dir[i][0];33             v.y = u.y + dir[i][1];34             v.d = u.d + 1;35             if(jud(v.x, v.y, v.d)){36                 if(g[v.x][v.y] == inf)//安全区域37                     return v.d;38                 vis[v.x][v.y] = 1;39                 q.push(v);40             }41         }42     }43     return -1;44 }45 int main(){46     int m, i, x, y, t;47     CLR(g,inf);48     scanf("%d", &m);49     for(i = 0; i < m; ++i){50         scanf("%d%d%d", &x, &y, &t);51         g[x][y] = min(t, g[x][y]);52         if(x > 0 && t < g[x-1][y])53             g[x-1][y] = t;54         if(y > 0 && t < g[x][y-1])55             g[x][y-1] = t;56         g[x+1][y] = min(t, g[x+1][y]);57         g[x][y+1] = min(t, g[x][y+1]);58     }59     if(g[0][0] == 0){printf("-1\n");return 0;}60     if(g[0][0] == inf){printf("0\n");return 0;}61     printf("%d\n",bfs());62     return 0;63 }
View Code

 

poj3669 Meteor Shower(BFS)