首页 > 代码库 > 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 }
poj3669 Meteor Shower(BFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。