神犬奇兵电视剧全集爱奇艺,中藏网,职业健康检查包括
Input
Output
Escaped in x minute(s).
Trapped!
Sample Input
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
Sample Output
Escaped in 11 minute(s). Trapped!
大致题意:给定一个三维的迷宫,求出到达终点的最短时间
表面很复杂但实际上只是三维的BFS就不多说了直接看代码吧
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<queue> 5 using namespace std; 6 struct node{ 7 int x,y,z,t; 8 }; 9 int l,r,c,sx,sy,sz,tx,ty,tz,ans; 10 bool map[35][35][35],vis[35][35][35]; 11 int dir[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}}; 12 bool check(int x,int y,int z) 13 { 14 if(x<0||y<0||z<0||x>r||y>c||z>l||map[x][y][z]==0||vis[x][y][z]) return 1; 15 return 0; 16 } 17 int bfs() 18 { 19 node now,next; 20 queue<node>q; 21 vis[sx][sy][sz]=1; 22 now.x=sx,now.y=sy,now.z=sz,now.t=0; 23 q.push(now); 24 while(!q.empty()) 25 { 26 now=q.front(); 27 q.pop(); 28 if(now.x==tx&&now.y==ty&&now.z==tz) return now.t; 29 for(int i=0;i<6;++i) 30 { 31 next.x=now.x+dir[i][0]; 32 next.y=now.y+dir[i][1]; 33 next.z=now.z+dir[i][2]; 34 if(check(next.x,next.y,next.z)) continue; 35 vis[next.x][next.y][next.z]=1; 36 next.t=now.t+1; 37 q.push(next); 38 } 39 } 40 return 0; 41 } 42 int main() 43 { 44 char s[35]; 45 while(1) 46 { 47 memset(map,0,sizeof(map)); 48 memset(vis,0,sizeof(vis)); 49 scanf("%d%d%d",&l,&r,&c); 50 if(l==0&&r==0&&c==0) return 0; 51 for(int i=1;i<=l;++i) 52 for(int j=1;j<=r;++j) 53 { 54 scanf("%s",s+1); 55 for(int g=1;g<=strlen(s);++g) 56 { 57 if(s[g]=='S') sx=j,sy=g,sz=i; 58 else if(s[g]=='E') tx=j,ty=g,tz=i,map[j][g][i]=1; 59 else if(s[g]=='.') map[j][g][i]=1; 60 else map[j][g][i]=0; 61 } 62 } 63 ans=bfs(); 64 if(ans) printf("Escaped in %d minute(s).\n",ans); 65 else printf("Trapped!\n"); 66 } 67 }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论