<传送门>

【题目大意】

给你一个三维的迷宫,让你计算从入口走到出口最少步数。

【题目分析】

其实和二维迷宫还是一样的,还是用队列来做,由于BFS算法一般是不需要回溯的,所以我们就用不着还用一个visit数组来记录是否访问过,直接将走过的结点置为不可走就可。

//Memory   Time
// 356K 32MS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
struct Node
{
int x,y,z;
int step;
};
queue<Node> que;
char Map[][][];
int sx,sy,sz;
int ex,ey,ez;
int dir_x[]={-,,,,,};
int dir_y[]={,,-,,,};
int dir_z[]={,,,,,-};
void read(int n,int row,int col)
{
int i,j,k;
for(i=;i<n;i++)
{
for(j=;j<row;j++)
{
for(k=;k<col;k++)
{
cin>>Map[i][j][k];
if(Map[i][j][k]=='S')
{
sx=i;
sy=j;
sz=k;
}
else if(Map[i][j][k]=='E')
{
ex=i;
ey=j;
ez=k;
}
}
getchar();
}
getchar();
}
} void BFS()
{
Node q;
q.x=sx;
q.y=sy;
q.z=sz;
q.step=;
que.push(q);
while(!que.empty())
{
Node tp=que.front();
que.pop();
int x=tp.x;
int y=tp.y;
int z=tp.z;
int step=tp.step;
for(int i=;i<;i++)
{
int tx=x+dir_x[i];
int ty=y+dir_y[i];
int tz=z+dir_z[i];
if(Map[tx][ty][tz]=='.')
{
Node Q;
Q.x=tx;
Q.y=ty;
Q.z=tz;
Q.step=step+;
que.push(Q);
Map[tx][ty][tz]='#';
}
else if(tx==ex&&ty==ey&&tz==ez)
{
cout<<"Escaped in "<<step+<<" minute(s)."<<endl;
return;
}
}
}
cout<<"Trapped!"<<endl;
} int main()
{
// freopen("cin.txt", "r", stdin);
int i, j, k;
int n,row,col;
while(cin>>n>>row>>col&&(n+row+col))
{
while(!que.empty()) que.pop();
getchar();
read(n,row,col);
BFS();
}
return ;
}

最新文章

  1. Linux iptables原理--数据包流向
  2. jQuery.my – 实时的复杂的双向数据绑定
  3. android 生命周期
  4. urlrewriter的使用
  5. 【自己动手】sublime text插件开发
  6. 3D Game Programming with directx 11 习题答案 8.2
  7. 【Android Developers Training】 37. 共享一个文件
  8. 记一次坑爹的RSA旅程____快哭了555555555(来自实验吧的warmup的wp和感想)
  9. 工厂模式(Factory Method)
  10. iOS开发之UIWebView的常见一些用法
  11. Ubuntu 14.04 安装 sysrepo v0.7.5
  12. Alertmanager 安装(k8s报警)
  13. HTML、CSS知识点,面试开发都会需要--No.4 内容布局
  14. grpc 使用流程、使用技巧
  15. 1.Dubbo2.5.3源码编译
  16. C++智能指针,指针容器原理及简单实现(auto_ptr,scoped_ptr,ptr_vector).
  17. nfd指令的详细说明
  18. idea svn 使用问题
  19. filebeat output redis 报错 i/o timeout
  20. 安装ffmpeg

热门文章

  1. java 8 学习三(Stream API)
  2. HDU 4828 小明系列故事——捉迷藏
  3. SpringCloud:搭建基于Gateway的微服务网关(二)
  4. E4A碰到打开自动闪退又自动打开又闪退一直循环的问题
  5. docker swarm 集群搭建
  6. 014 Mui
  7. Java基础 awt Button 点击按钮后在控制台输出文字
  8. postgre查询一段时间内的数据
  9. Eclipse检出原MyEclipse项目后 javax.servlet.http相关类都报错【我,体现着一类jar包问题的处理方法】
  10. windows中设置php环境变量