poj2627
题意:知道起点和终点，同时知道飞行速度和能在外面飞行的最长时间，问最小经过多少个洞可以到达终点
分析:裸的bfs
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=2020; 15 typedef struct P 16 { 17 double x,y; 18 int rec; 19 bool vis; 20 }P; 21 P p[maxn]; 22 double sx,sy,gx,gy; 23 double distance(double x1,double y1,double x2,double y2) 24 { 25 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); 26 } 27 double v,m; 28 int main() 29 { 30 cin>>v>>m; 31 cin>>sx>>sy>>gx>>gy; 32 int h=1; 33 while(cin>>p[h].x>>p[h].y) 34 { 35 p[h].rec=0; 36 p[h].vis=false; 37 h++; 38 } 39 double dist=v*m*60; 40 if(distance(sx,sy,gx,gy)<=dist) 41 { 42 cout<<"Yes, visiting 0 other holes."<<endl; 43 return 0; 44 } 45 P s; 46 queue<P> que; 47 s.x=sx,s.y=sy,s.rec=0,s.vis=true; 48 que.push(s); 49 int ans=0x3ffff; 50 int flag=0; 51 while(!que.empty()) 52 { 53 P t=que.front(); 54 que.pop(); 55 if(distance(t.x,t.y,gx,gy)<=dist) 56 { 57 flag=1; 58 ans=min(ans,t.rec); 59 } 60 for(int i=1;i<h;i++) 61 { 62 if(distance(t.x,t.y,p[i].x,p[i].y)>dist||p[i].vis==true) 63 continue; 64 p[i].rec=t.rec+1; 65 p[i].vis=true; 66 que.push(p[i]); 67 } 68 } 69 if(flag) 70 cout<<"Yes, visiting "<<ans<<" other holes."<<endl; 71 else 72 cout<<"No. "<<endl; 73 return 0; 74 }
poj2251
题意:在一个三维空间里面进行求最短路径
分析:与上面一题相同，bfs进行操作，注意这次扫的是六个方向
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 int l,r,c; 15 const int maxn=50; 16 typedef struct P 17 { 18 char c; 19 int x,y; 20 int id; 21 int rec; 22 }P; 23 P s[maxn][maxn][maxn]; 24 int vis[maxn][maxn][maxn]; 25 int ans; 26 int flag; 27 int dx[]={-1,1,0,0,0,0},dy[]={0,0,-1,1,0,0},dz[]={0,0,0,0,1,-1}; 28 void bfs(int sx,int sy,int sz,int gx,int gy,int gz) 29 { 30 queue<P>p; 31 if(sx==gx&&sy==gy&&sz==gy) 32 { 33 flag=1; 34 ans=0; 35 } 36 else 37 { 38 p.push(s[sz][sx][sy]); 39 vis[sz][sx][sy]=1; 40 int nx=sx,ny=sy,nz=sz; 41 while(!p.empty()) 42 { 43 P t=p.front(); 44 p.pop(); 45 for(int i=0;i<6;i++) 46 { 47 nx=t.x+dx[i]; 48 ny=t.y+dy[i]; 49 nz=t.id+dz[i]; 50 if(ny<c&&ny>=0&&nx<r&&nx>=0&&nz>=1&&nz<=l&&!vis[nz][nx][ny]) 51 { 52 vis[nz][nx][ny]=1; 53 if(s[nz][nx][ny].c=='.'){ 54 s[nz][nx][ny].rec=t.rec+1; 55 p.push(s[nz][nx][ny]); 56 } 57 if(nx==gx&&ny==gy&&nz==gz) 58 { 59 flag=1; 60 ans=min(ans,(t.rec+1)); 61 } 62 } 63 } 64 } 65 } 66 } 67 int main() 68 { 69 while(cin>>l>>r>>c) 70 { 71 if(l==0&&r==0&&c==0) break; 72 for(int i=1;i<=l;i++) 73 for(int j=0;j<r;j++) 74 for(int k=0;k<c;k++) 75 { 76 cin>>s[i][j][k].c; 77 s[i][j][k].x=j; 78 s[i][j][k].y=k; 79 s[i][j][k].id=i; 80 s[i][j][k].rec=0; 81 } 82 int sx,sy,sz,gx,gy,gz; 83 for(int i=1;i<=l;i++) 84 for(int j=0;j<r;j++) 85 for(int k=0;k<c;k++) 86 { 87 if(s[i][j][k].c=='S') 88 { 89 sx=j,sy=k,sz=i; 90 }else if(s[i][j][k].c=='E'){ 91 gx=j,gy=k,gz=i; 92 } 93 } 94 memset(vis,0,sizeof(vis)); 95 ans=0x3ffff; 96 flag=0; 97 bfs(sx,sy,sz,gx,gy,gz); 98 if(flag) 99 cout<<"Escaped in "<<ans<<" minute(s)."<<endl; 100 else 101 cout<<"Trapped!"<<endl; 102 } 103 return 0; 104 }