Description

  You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.

  Is an escape possible? If yes, how long will it take?

  一个三维的迷宫问题,和二维没什么区别,直接BFS就好。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue> using namespace std; bool map1[][][];
bool vis[][][];
int L,R,C;
int Sl,Sr,Sc,El,Er,Ec; struct state
{
int l,r,c;
int num; state() {}
state(int x,int y,int z,int n):l(x),r(y),c(z),num(n) {}
}; bool judge(int x,int y,int z)
{
if(x<=||x>L||y<=||y>R||z<=||z>C)
return ; if(map1[x][y][z]==)
return ; if(vis[x][y][z])
return ; vis[x][y][z]=;
return ;
} int bfs()
{
queue <state> que;
state temp;
int tl,tr,tc; que.push(state(Sl,Sr,Sc,)); while(!que.empty())
{
temp=que.front();
que.pop(); if(temp.l==El&&temp.r==Er&&temp.c==Ec)
return temp.num; tl=temp.l;
tr=temp.r;
tc=temp.c; if(judge(tl-,tr,tc))
que.push(state(tl-,tr,tc,temp.num+));
if(judge(tl+,tr,tc))
que.push(state(tl+,tr,tc,temp.num+));
if(judge(tl,tr-,tc))
que.push(state(tl,tr-,tc,temp.num+));
if(judge(tl,tr+,tc))
que.push(state(tl,tr+,tc,temp.num+));
if(judge(tl,tr,tc-))
que.push(state(tl,tr,tc-,temp.num+));
if(judge(tl,tr,tc+))
que.push(state(tl,tr,tc+,temp.num+));
} return -;
} int main()
{
char s[];
int ans; ios::sync_with_stdio(false); while(cin>>L>>R>>C)
{
memset(vis,,sizeof(vis)); if(!L&&!R&&!C)
break; for(int i=;i<=L;++i)
for(int j=;j<=R;++j)
{
cin>>s;
for(int k=;k<=C;++k)
switch(s[k-])
{
case 'S':
Sl=i;
Sr=j;
Sc=k;
map1[i][j][k]=;
break;
case 'E':
El=i;
Er=j;
Ec=k;
map1[i][j][k]=;
break;
case '.':
map1[i][j][k]=;
break;
case '#':
map1[i][j][k]=;
break;
}
} ans=bfs(); if(ans!=-)
cout<<"Escaped in "<<ans<<" minute(s).\n";
else
cout<<"Trapped!\n";
} return ;
}

最新文章

  1. Java使用Fork/Join框架来并行执行任务
  2. Url获取图片流并打包~
  3. mysql online ddl
  4. UVa1593_Allgnment_Of_Code
  5. BRIEF 特征描述子
  6. 解决ADT升级报错
  7. android: 调用摄像头拍照
  8. Python Socket,How to Create Socket Cilent? - 网络编程实例
  9. linux服务之NFS和SAMBA服务
  10. 用shell统计访问日志里每个ip访问次数【转】
  11. MYSQL和JAVA(课堂笔记)
  12. tensorflow Pipeline 之TextLineReader 和decode_csv多分割替代方案
  13. JAVA程序员面试30问(附带答案)
  14. 将服务器文件上传到ftp shell操作
  15. QT中添加工具条QToolBar
  16. POJ 3580-SuperMemo-splay树
  17. UNIX网络编程读书笔记:I/O模型(阻塞、非阻塞、I/O复用、信号驱动、异步)
  18. [翻译]Review——24 tips for React Native you probably want to know
  19. 转!!ftp的主动模式(port)与被动模式(PASV)
  20. UVA_1434_YAPTCHA

热门文章

  1. Enum 枚举基础
  2. 第一个前台页面----xflow的页面
  3. GameUnity 2.0 文档(四) 网格+四叉树 最优碰撞检测
  4. 模版引擎Handlebars语法(1)
  5. 分布式数据库Cobar
  6. Roboguice学习之视图注入
  7. AS--&gt;如何更高效的使用 Gradle, 快速build apk
  8. JSON缺包导致的错误
  9. Ubuntu将新增磁盘挂载到home下
  10. wind7系统修改host