/**
***= =最近懒得没有发表一篇文章,自觉羞愧...于是发表几篇小文以弥胡哥对我的期盼之情...
翻译一下: 一个房间,3维的,指定他的3个维度的大小,然后指定他的每个单位的内容(= =w 天哪poj你好烦),#代表该单位无法通过,.代表可以通过,S代表可怜的主人公所在位置,E代表光明的出口所在的位置。求该主人公能否逃脱,能在最少多少次的操作后逃脱(话说这题翻译过来是地下城...好吧,槽点略多)
描述
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?
输入
The input consists of a number of dungeons.
Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon.
A cell full of rock is indicated by a '#' and empty cells are represented by a '.'.
Your starting position is indicated by 'S' and the exit by the letter 'E'.
There's a single blank line after each level.
Input is terminated by three zeroes for L, R and C.
输出
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!
样例输入
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
样例输出
Escaped in 11 minute(s).
Trapped!
*/
#include<iostream>
#include<string.h>
#include<string>
#include<queue>
using namespace std;
//
class Point{
public:
Point(int x,int y,int z){
this->x = x;
this->y = y;
this->z = z;
}
bool equals(Point p){
return (x==p.x && y==p.y && z==p.z);
}
int x;
int y;
int z;
};
void test(int L,int R,int C){
if(L<=30 && R<=30 && C<=30){//万恶的英语,题目limit to是<=的意思
int ROOM[L][R][C];
int NUMofS = 0;//S的个数
int NUMofE = 0;//E的个数
bool able = true;//此属性决定了该输入能否进行,包含了格式输出错误,个数错误等情况
int x0,y0,z0;//主人公的位置
int x1,y1,z1; //出口的位置
string s;
memset(ROOM,0,sizeof(ROOM));//将所有的内容都赋予0值
for(int i = 0;i < L;i++){
for(int j = 0;j < R;j++){
cin>>s;
if(s.length()>C)able = false;
for(int k = 0;k < C;k++){
char ch = s.at(k);//通过输入的字符来决定该位置的内容值
switch(ch){
case '#' :
ROOM[i][j][k] = -1;//-1即无法通过
break;
case '.' ://可以通过,默认为0
break;
case 'S' :
x0 = i;
y0 = j;
z0 = k;
NUMofS++;
if(NUMofS>1)
able = false;
break;
case 'E' :
x1 = i;
y1 = j;
z1 = k;
NUMofE++;
if(NUMofE>1)
able = false;
break;
default :
able = false;
}
}
}
}
if(able == false){//感觉题目设置的不严谨,因为输入格式错误的话,题目没有说明要怎么解决,不过经过多次的wa测试,上述情况应该输出无法通过的语句
cout<<"Trapped!"<<endl;
return;
}
Point from(x0,y0,z0);
Point to(x1,y1,z1);
queue<Point> p;
p.push(from);
while(!p.empty()){
Point xp = p.front();
p.pop();
if(xp.equals(to)){//搜到了相同的点就输出
cout<<"Escaped in "<<ROOM[to.x][to.y][to.z]<<" minute(s)."<<endl;
return;
}else{
for(int i = 0;i < 6;i++){
switch(i){
case 0 ://x方向-1
if(xp.x-1>=0 && !ROOM[xp.x-1][xp.y][xp.z]){
Point np(xp.x-1,xp.y,xp.z);
if(!np.equals(from)){
p.push(np);
ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
}
}
break;
case 1 ://x方向+1
if(xp.x+1<L && !ROOM[xp.x+1][xp.y][xp.z]){
Point np(xp.x+1,xp.y,xp.z);
if(!np.equals(from)){
p.push(np);
ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
}
}
break;
case 2 ://y方向-1
if(xp.y-1>=0 && !ROOM[xp.x][xp.y-1][xp.z]){
Point np(xp.x,xp.y-1,xp.z);
if(!np.equals(from)){
p.push(np);
ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
}
}
break;
case 3 ://y方向+1
if(xp.y+1<R && !ROOM[xp.x][xp.y+1][xp.z]){
Point np(xp.x,xp.y+1,xp.z);
if(!np.equals(from)){
p.push(np);
ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
}
}
break;
case 4 ://z方向-1
if(xp.z-1>=0 && !ROOM[xp.x][xp.y][xp.z-1]){
Point np(xp.x,xp.y,xp.z-1);
if(!np.equals(from)){
p.push(np);
ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
}
}
break;
case 5 ://z方向+1
if(xp.z+1<C && !ROOM[xp.x][xp.y][xp.z+1]){
Point np(xp.x,xp.y,xp.z+1);
if(!np.equals(from)){
p.push(np);
ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
}
}
break;
default :
cout<<"Trapped!"<<endl;
return;
}
}
}
}
cout<<"Trapped!"<<endl;
}
}
int main(){
int L,R,C;
cin>>L>>R>>C;
while(L&&R&&C){
test(L,R,C);
cin>>L>>R>>C;
}
return 0;
}
相关推荐
WEB程序设计大作业 实现多个网页的互联功能 界面漂亮 实用
mfc可视化程序设计的大作业俄罗斯方块,windows应用程序,visual studio2013下开发
2013级,C++程序设计课件。第3章 程序设计初步。内容: 3.1 面向过程程序设计和算法 3.2 C++程序和语句 3.3 赋值语句 3.4 C++的输入与输出 3.5 编写顺序结构的程序 3.6 关系运算和逻辑运算 3.7 选择结构和 if 语句 ...
《软件工程》大型作业-网上书店管理系统分析、设计及实现
本系统实现的主要功能就是学生在线提交实验报告,教师在线批阅实验报告的功能。用PHP语言开发完成,文档内容结构如下: 1系统分析 1.1功能 1.2解决方案 2.系统设计 2.1.1系统流程图 2.1.2 应用程序的文件描述 ...
程序设计语言 实践之路 第3版 英文原版 包含PDF,CHM,CD,源码
习题集内容覆盖面广,包括:Java言的基本常识、基本语法、面向对象的基本概念、数组、字符串、异常处理、文件和数据流、图形用户界面设计、小应用程序、线程、编程规范、网络程序设计、多媒体民图形学程序设计以及...
《C++程序设计教程》(修订版)—设计思想与实现 钱能著 课后习题答案详解、源代码
要求:1、用C语言实现程序设计; 2、利用结构体数组、链表等实现学生信息表达、查询等,充分体现数据结构的知识; 3、系统的各个功能模块要求用函数的形式实现; 4、界面友好(良好的人机交互),程序要有注释。 5、...
研究生网络编程作业,所有的结构与代码均由自己实现,适合用于上交老师布置的聊天程序编写作业
北京大学信息科学技术学院的课程程序设计实习的大作业魔兽世界终极版的源代码,仅供参考。
为适应计算机基础不同的读者学习与欣赏,对有些趣题采用多种思路设计与多个程序实现。其中少量难度较大、要求较高的问题在目录中用“*”标注,可供在校学习“C程序设计”课程的同学们进行课程设计时选用。 《趣味C...
实战MATLAB之并行程序设计
《PHP与MySQL程序设计 第4版 》pdf与源码 是全面讲述PHP与MySQL的经典之作 书中不但全面介绍了两种技术的核心特性 还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序 《PHP与MySQL程序设计 第4版 》...
张玉生《C语言程序设计》双色版 教材课后习题答案,仅供参考,大家一定要自己做一遍再校对答案,实验书的答案已经以文章的形式发布了。
WPF程序设计指南(最全-清晰PDF中文版-附源码) (文件太大,分成三个部分) 跟随Windows大师Charles Petzold学习新一代Windows客户端接口程序设计 Windows Presentation Foundation(WPF)是微软.NET Fmmework 3.0...
GDI+程序设计.pdf,书籍和随书源码。
第3章 设计与实现 48 3.1 马尔可夫链算法 48 3.2 数据结构的选择 50 3.3 在C中构造数据结构 51 3.4 生成输出 54 3.5 Java 56 3.6 C++ 59 3.7 Awk和Perl 61 3.8 性能 63 3.9 经验教训 64 第4章 界面 67 4.1 逗号分隔...
《C程序设计语言<第2版新版>习题解答(原书第2版)》是对Brian W.Kernighan和Dennis M.Ritchie所著的《C程序设计语言<第2版新版>习题解答(原书第2版)》所有练习题的解答,是极佳的编程实战辅导书。K&R的著作是C语言...
第1篇(第1~10章)为autollsp程序设计基础篇,主要介绍了autollsp的基本结构、语法、功能函数、对象属性、循环、判断式、子程序、选择集、符号表、读文件以及写文件等autolisp程序设计的相关知识与技巧。第2篇(第11章...