文档章节

先放一下之前c++的BFS,然后试着拿php写一下

侯禹
 侯禹
发布于 2013/07/29 20:31
字数 655
阅读 46
收藏 0

 

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?  

Input

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.

Output

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!

Sample Input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

Sample Output

其实就是个三维的宽搜,小弟代码写的,不好勿喷。。。。。。。

 

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
struct point
{
  int x,y,z;
};
queue <point>que;
    int l,r,c;
point start,end,cur,pre;
int ans;
int xx,yy,zz;
char chess[32][32][32];
int ch[32][32][32];
int visit[32][32][32];
void path(int x,int y,int z,int t)
{
    switch(t)
    {
        case 0:xx=x+1;yy=y;zz=z;break;
        case 1:xx=x;yy=y+1;zz=z;break;
        case 2:xx=x;yy=y;zz=z+1;break;
        case 3:xx=x-1;yy=y;zz=z;break;
        case 4:xx=x;yy=y-1;zz=z;break;
        case 5:xx=x;yy=y;zz=z-1;break;
    }
    return ;
}
int bfs()
{
    que.push(start);
    visit[start.z][start.y][start.x]=1;
    while(!que.empty())
    {
        cur=que.front();
        que.pop();
        if(cur.x==end.x&&cur.y==end.y&&cur.z==end.z)
        {
            return visit[end.z][end.y][end.x];
        }
        for(int i=0;i<6;i++)
        {
            path(cur.x,cur.y,cur.z,i);
if(xx>=0&&yy>=0&&zz>=0&&zz<l&&xx<c&&yy<r&&visit[zz][yy][xx]==0&&ch[zz][yy][xx]==1)
            {
//cout<<"okz:"<<zz<<"oky:"<<yy<<"okx:"<<xx<<endl;
                pre.x=xx;
                pre.y=yy;
                pre.z=zz;
                visit[zz][yy][xx]=visit[cur.z][cur.y][cur.x]+1;
                que.push(pre);
                 }
        }

    }
return 0;
}
int main(void)
{//freopen("r.txt","r",stdin);
    while(cin>>l>>r>>c&&l+r+c!=0)
    {
        memset(chess,0,sizeof(chess));
        memset(ch,0,sizeof(ch));
        memset(visit,0,sizeof(visit));
        for(int i=0;i<l;i++)
        {
            for(int j=0;j<r;j++)
            {
                cin>>chess[i][j];
                for(int k=0;k<c;k++)
                {
                    if(chess[i][j][k]=='.')
                    ch[i][j][k]=1;
                    else if(chess[i][j][k]=='#')
                    ch[i][j][k]=0;
                   else if(chess[i][j][k]=='S')
                   {ch[i][j][k]=1;
                        start.x=k;
                        start.y=j;
                        start.z=i;
                    }
                    else if(chess[i][j][k]=='E')
                   {ch[i][j][k]=1;
                        end.x=k;
                        end.y=j;
                        end.z=i;
                    }
                }
            }
 
        }
        //cout<<"xyz"<<end.x<<end.y<<end.z<<endl;
        int t=bfs();
        while(!que.empty())que.pop();
        if(t!=0)
        cout<<"Escaped in "<<t-1<<" minute(s)."<<endl;
            else
            cout<<"Trapped!"<<endl;

    }
 
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 96
博文 49
码字总数 34362
作品 0
海淀
程序员
私信 提问
Cocos2d-X游戏工具开发之一:将Cocos2d-X嵌入MFC的子窗体方法讲解

[Cocos2d-x相关教程来源于红孩儿的游戏编程之路 CSDN博客地址:http://blog.csdn.net/honghaier] 红孩儿Cocos2d-X学习园地QQ群:249941957 加群写:Cocos2d-x 另本章为我的Cocos2d-x教程一书...

长平狐
2013/03/19
60
0
Cocos2d-x2.0 进度动画 深入分析

[Cocos2d-x相关教程来源于红孩儿的游戏编程之路CSDN博客地址:http://blog.csdn.net/honghaier] 红孩儿Cocos2d-X学习园地QQ2群:44208467 加群写:Cocos2d-x 红孩儿Cocos2d-X学习园地QQ群:2...

长平狐
2013/03/19
581
0
C++与Flash的交互

研究Flash嵌入游戏中的可行性....... 渲染问题已解决 事件响应已解决 下面是C++与Flash AS的交互, 以MFC为例: 1. 新建一个MFC Dialog程序 2. 添加一个Flash控件 3. 把Flash控件添加一个变量 ...

长平狐
2012/11/12
2K
0
Cocos2d-X游戏工具开发之一:将Cocos2d-X嵌入MFC的子窗体方法讲解

[Cocos2d-x相关教程来源于红孩儿的游戏编程之路 CSDN博客地址:http://blog.csdn.net/honghaier] 红孩儿Cocos2d-X学习园地QQ群:249941957 加群写:Cocos2d-x 另本章为我的Cocos2d-x教程一书...

长平狐
2012/11/19
934
0
C++ STL编程轻松入门 4

 2.2.2 第二版:工业时代--组件化大生产   我们应该庆幸自己所生活的年代。工业时代,科技的发展所带来的巨大便利已经影响到了我们生活中的每个细节。如果你还在以原始人类的方式生活着,...

暖冰
2015/11/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周三乱弹 —— 有一天考拉麻麻拉肚子了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @瘟神灬念 :分享周汇洋的单曲《Man Srae(曼斯拉之舞)》:美滋滋。。。。 手机党少年们想听歌,请使劲儿戳(这里) 我听了一下 赶紧关了, ...

小小编辑
39分钟前
12
3
oh-my-zsh 自定义

GitHub 地址 基于 oh-my-zsh 的自定义配置,增加了一些个人常用插件与皮肤。 采用的是 git submodule 来维护,包括 oh-my-zsh,之所以这么搞,主要是手头有多台 linux 需要维护, 每台机器、...

郁也风
今天
6
0
Docker安装踩坑:E_FAIL 0x80004005的解决

参考 菜鸟教程--Windows Docker 安装 http://www.runoob.com/docker/windows-docker-install.html 官方文档-Install Docker Toolbox on Windows https://docs.docker.com/toolbox/toolbox_in......

karma123
今天
6
0
js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
昨天
18
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
昨天
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部