POJ - 2251 Dungeon Master
2018-07-29 08:37:57来源:博客园 阅读 ()
Is an escape possible? If yes, how long will it take?
Input
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- POJ-3278 2020-04-01
- Asteroids!_poj2225 2020-02-09
- poj-1753题题解思路 2020-01-26
- POJ1852 2019-11-11
- POJ2431 优先队列+贪心 - biaobiao88 2019-11-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash