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