首页 > 代码库 > （BFS）poj3669-Meteor Shower

（BFS）poj3669-Meteor Shower

2024-08-24 15:35:41   220人阅读

题目地址

　　为判断某时刻能否走到某位置，建立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


联系
我们