首页 > 代码库 > poj2251Dungeon Master(bfs模板题)
poj2251Dungeon Master(bfs模板题)
题目链接:http://poj.org/problem?id=2251
可以说是bfs的模板题了。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<queue> 5 using namespace std; 6 char pic[32][32][32]; 7 int vis[32][32][32]; 8 int dir[6][3]={0,0,1,0,0,-1,1,0,0,-1,0,0,0,1,0,0,-1,0}; 9 10 int ex,ey,ez; 11 int l,n,m; 12 13 struct node 14 { 15 int x,y,z; 16 int d; 17 }now,nex; 18 19 20 21 int bfs() 22 { 23 24 queue<node> q; 25 now.d=0; 26 q.push(now); 27 while(!q.empty()) 28 { 29 now=q.front(); 30 q.pop(); 31 if(now.x==ex&&now.y==ey&&now.z==ez) return now.d; 32 for(int i=0;i<6;i++) 33 { 34 nex.x=now.x+dir[i][0]; 35 nex.y=now.y+dir[i][1]; 36 nex.z=now.z+dir[i][2]; 37 if(!vis[nex.x][nex.y][nex.z]&&pic[nex.x][nex.y][nex.z]!=‘#‘ 38 &&nex.x>=0&&nex.x<l&&nex.y>=0&&nex.y<n&&nex.z>=0&&nex.z<m) 39 { 40 nex.d=now.d+1; 41 vis[nex.x][nex.y][nex.z]=1; 42 q.push(nex); 43 } 44 } 45 } 46 return -1; 47 48 } 49 50 int main() 51 { 52 while(scanf("%d%d%d",&l,&n,&m)!=EOF&&(m||n||l)) 53 { 54 memset(vis,0,sizeof(vis)); 55 56 for(int i=0;i<l;i++) 57 for(int j=0;j<n;j++) 58 for(int k=0;k<m;k++) 59 { 60 cin>>pic[i][j][k]; 61 if(pic[i][j][k]==‘S‘) {vis[i][j][k]=1;now.x=i;now.y=j;now.z=k;} 62 if(pic[i][j][k]==‘E‘) {ex=i;ey=j;ez=k;} 63 64 } 65 int st=bfs(); 66 if(st==-1) puts("Trapped!"); 67 else printf("Escaped in %d minute(s).\n", st); 68 } 69 return 0; 70 }
poj2251Dungeon Master(bfs模板题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。