图论 --- 三维空间bfs
2024-10-13 00:46:31
【题目大意】
给你一个三维的迷宫,让你计算从入口走到出口最少步数。
【题目分析】
其实和二维迷宫还是一样的,还是用队列来做,由于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 ;
}
最新文章
- Linux iptables原理--数据包流向
- jQuery.my – 实时的复杂的双向数据绑定
- android 生命周期
- urlrewriter的使用
- 【自己动手】sublime text插件开发
- 3D Game Programming with directx 11 习题答案 8.2
- 【Android Developers Training】 37. 共享一个文件
- 记一次坑爹的RSA旅程____快哭了555555555(来自实验吧的warmup的wp和感想)
- 工厂模式(Factory Method)
- iOS开发之UIWebView的常见一些用法
- Ubuntu 14.04 安装 sysrepo v0.7.5
- Alertmanager 安装(k8s报警)
- HTML、CSS知识点,面试开发都会需要--No.4 内容布局
- grpc 使用流程、使用技巧
- 1.Dubbo2.5.3源码编译
- C++智能指针,指针容器原理及简单实现(auto_ptr,scoped_ptr,ptr_vector).
- nfd指令的详细说明
- idea svn 使用问题
- filebeat output redis 报错 i/o timeout
- 安装ffmpeg