Dungeon Master
2024-08-28 16:10:03
poj2251:http://poj.org/problem?id=2251
题意:给你一个三维的立方体,然后给你一个起点,和终点的坐标。然后让你求从起点到终点的最短路程。
题解:该题就是求三维的最短路,可以采用BFS,三维的BFS。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int counts[][][];//记录到起点的最短距离
struct Node{
int x;
int y;
int z;
int step;
};
int n,m,l;//长,宽,高
char map1[][][];//原来的三维的地图
int startx,starty,startz;//起点坐标
int endx,endy,endz;//终点坐标
int BFS(int x,int y,int z){
int xxx[]={,,,,-,};
int yyy[]={,,-,,,};
int zzz[]={-,,,,,};//六个方向的对应的3个坐标
for(int i=;i<=l;i++)
for(int j=;j<=n;j++)
for(int k=;k<=m;k++)//初始化
counts[i][j][k]=;
counts[x][y][z]=;//注意这里的初始化
queue<Node>Q;
Node tt;
tt.x=x;tt.y=y;tt.z=z;tt.step=;
Q.push(tt);
while(!Q.empty()){
Node temp=Q.front();
Q.pop();
int xx=temp.x;
int yy=temp.y;
int zz=temp.z;
int step=temp.step;
for(int i=;i<;i++){//六个方向进行搜索
if(xx+xxx[i]>=&&xx+xxx[i]<=n&&yy+yyy[i]>=&&yy+yyy[i]<=m&&zz+zzz[i]>=&&zz+zzz[i]<=l){
if(map1[zz+zzz[i]][xx+xxx[i]][yy+yyy[i]]!='#'&&step+<counts[zz+zzz[i]][xx+xxx[i]][yy+yyy[i]]){
counts[zz+zzz[i]][xx+xxx[i]][yy+yyy[i]]=step+;
Node ttt;
ttt.x=xx+xxx[i];
ttt.y=yy+yyy[i];
ttt.z=zz+zzz[i];
ttt.step=step+;
Q.push(ttt);
}
}
}
}
return counts[endz][endx][endy];//返回终点距离 }
int main(){
while(~scanf("%d%d%d",&l,&n,&m)&&l&&n&&m){
for(int i=;i<=l;i++){
for(int j=;j<=n;j++){
for(int k=;k<=m;k++){
cin>>map1[i][j][k];
if(map1[i][j][k]=='S'){
startz=i;
startx=j;
starty=k;
}
if(map1[i][j][k]=='E'){
endz=i;
endx=j;
endy=k;
}
}
}
}
int ans=BFS(startx,starty,startz);
if(ans==)
printf("Trapped!\n");
else
printf("Escaped in %d minute(s).\n",ans);
} }
最新文章
- Spark ZooKeeper数据恢复
- Python学习路程day20
- rhel 5.8下静默安装oracle11gr2
- Swift - 多行文本输入框(UITextView)
- .NET指定程序集的位置
- Jquery 查看DOM上绑定的事件列表
- Demo学习: CalendarPanel
- Mybatis在oracle、mysql、db2、sql server的like模糊查询
- 老李分享:robotium3.6与4.0 later 的区别 1
- 201521123057 《Java程序设计》第2周学习总结
- SpringBoot整合Netty并使用Protobuf进行数据传输(附工程)
- php 通过curl header传值
- git 入门教程之安装 git
- spring mvc注解版01
- Linq多表联合查询,在View中绑定数据
- node.js初识04
- bootstrap图片上传功能
- 各组Beta版本发布点评
- SQL:获取中文周几
- lucene之中文分词及其高亮显示