POJ 2251 Dungeon Master(BFS)
2018-06-17 22:14:11来源:未知 阅读 ()
题目网址:http://poj.org/problem?id=2251
题目:
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 34733 | Accepted: 13268 |
Description
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!
思路:
这道题无非就是将方向数组再增加一个维度——层数。由原来的四个方向,延伸为6个方向,多了上楼和下楼。总而言之就是换汤不换药,直接BFS。要注意的是每次搜索完都要清空一下队列。
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 const int INF=111111111; 6 struct node{ 7 int z,x,y; 8 }dir[6]={{0,1,0},{0,-1,0},{0,0,1},{0,0,-1},{-1,0,0},{1,0,0}}; 9 queue<node>q; 10 int l,r,c; 11 int xb,yb,zb,xe,ye,ze; 12 int visited[35][35][35]; 13 int flag; 14 char maze[35][35][35]; 15 bool check(int z,int x,int y){ 16 if(z<0 || z>=l) return false; 17 if(x<0 || x>=r) return false; 18 if(y<0 || y>=c) return false; 19 if(maze[z][x][y]=='#') return false;//这里的判断条件不要写成maze[z][x][y]!='.',因为还有结束标记'E'也是要走的 20 if(visited[z][x][y]) return false;//走过的点无需再走,因为再经过该点时说明耗费的时间已经比之前久了,所以不用考虑 21 return true; 22 } 23 void init(){ 24 memset(visited, 0, sizeof(visited)); 25 flag=0; 26 while (!q.empty()) q.pop();//记住每次清空队列 27 } 28 void bfs(){ 29 node now,next; 30 now.z=zb;now.x=xb;now.y=yb; 31 q.push(now); 32 while (!q.empty()) { 33 now=q.front();q.pop(); 34 if(now.z==ze && now.x==xe && now.y==ye){ 35 flag=1; 36 printf("Escaped in %d minute(s).\n",visited[now.z][now.x][now.y]-1);//因为起点是从1开始标记,所以答案减一 37 break; 38 } 39 for(int d=0;d<6;d++){ 40 next.z=now.z+dir[d].z; 41 next.x=now.x+dir[d].x; 42 next.y=now.y+dir[d].y; 43 if(check(next.z,next.x,next.y)){ 44 visited[next.z][next.x][next.y]=visited[now.z][now.x][now.y]+1; 45 q.push(next); 46 } 47 } 48 } 49 } 50 int main(){ 51 while(scanf("%d%d%d ",&l,&r,&c)!=EOF && (l+r+c)){ 52 init(); 53 for (int i=0; i<l; i++) { 54 for (int j=0; j<r; j++) { 55 gets(maze[i][j]); 56 for(int k=0; k<c; k++){ 57 if(maze[i][j][k]=='S'){ 58 zb=i;xb=j;yb=k; 59 } 60 if(maze[i][j][k]=='E'){ 61 ze=i;xe=j;ye=k; 62 } 63 } 64 } 65 char str[100]; 66 gets(str); 67 } 68 visited[zb][xb][yb]=1;//起点要先标记走过 69 bfs(); 70 if(!flag) printf("Trapped!\n"); 71 } 72 return 0; 73 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系: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