首页 > 代码库 > (BFS)poj3669-Meteor Shower
(BFS)poj3669-Meteor Shower
题目地址
为判断某时刻能否走到某位置,建立shi数组,记录某位置最早t时刻就不能走。(初始化为-1)之后开始从(0,0)出发bfs,用bu数组记录走到某一位置时花费的步数,并且需要用vi数组记录是否走到过某个位置,不然慧反复走出错。注意可走的范围是第一象限,只是输入的陨石掉落位置是0——300。(之前因为这个判断位置是否合法WA了……)。
参考代码:
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include <iostream> 5 using namespace std; 6 int shi[305][305],m,bu[305][305],dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 7 bool vi[305][305]; 8 typedef pair<int ,int >P; 9 int si,sj,t; 10 int bfs() 11 { 12 queue<P> que; 13 P p; 14 que.push(P(0,0)); 15 while(que.size()) 16 { 17 p=que.front(); 18 que.pop(); 19 if(shi[p.first][p.second]==-1) 20 return bu[p.first][p.second]; 21 int i,xx,yy; 22 for(i=0;i<4;i++) 23 { 24 xx=p.first+dir[i][0]; 25 yy=p.second+dir[i][1]; 26 if(xx>=0&&xx<=302&&yy>=0&&yy<=302&&(shi[xx][yy]==-1||bu[p.first][p.second]+1<shi[xx][yy])&&!vi[xx][yy]) 27 { 28 que.push(P(xx,yy)); 29 bu[xx][yy]=bu[p.first][p.second]+1; 30 vi[xx][yy]=true; 31 } 32 } 33 } 34 return -1; 35 } 36 int main() 37 { 38 memset(shi,-1,sizeof(shi)); 39 memset(bu,0,sizeof(bu)); 40 memset(vi,false,sizeof(vi)); 41 scanf("%d",&m); 42 int i,an; 43 while(m--) 44 { 45 scanf("%d%d%d",&si,&sj,&t); 46 if(shi[si][sj]==-1||shi[si][sj]>t) 47 shi[si][sj]=t; 48 for(i=0;i<4;i++) 49 { 50 int xx,yy; 51 xx=si+dir[i][0]; 52 yy=sj+dir[i][1]; 53 if(xx>=0&&xx<=302&&yy>=0&&yy<=302&&(shi[xx][yy]>t||shi[xx][yy]==-1)) 54 shi[xx][yy]=t; 55 } 56 } 57 vi[0][0]=true; 58 an=bfs(); 59 printf("%d\n",an); 60 return 0; 61 }
(BFS)poj3669-Meteor Shower
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。