文档章节

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

侯禹
 侯禹
发布于 2013/07/29 20:31
字数 655
阅读 45
收藏 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;

    }
 
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 95
博文 49
码字总数 34362
作品 0
海淀
程序员
C++ STL编程轻松入门 4

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

暖冰
2015/11/21
0
0
POJ 1979: Red and Black

题目在此 解题思路:直接 DFS 或 BFS 就行了。 之前被 STL 拖过后腿,偏执劲儿又上来了,这次刻意不用 std::queue,自己写队列,BFS 不用递归,结果就是……代码又臭又长,让人不忍直视…… ...

Alexander_zhou
2014/02/24
0
0
C++灵魂所在之---多态的前世与今生

开头先送大家一句话吧: 众所周知,在20世纪80年代早期,C++在贝尔实验室诞生了,这是一门面向对象的语言,但它又不是全新的面向对象的语言,它是在传统的语言(C语言)进行面向对象扩展而来...

loving_forever_
2016/06/13
0
0
OpenWRT开发之——对C++的支持(解决库依赖问题)

C++是本人的强项。如果在OpenWrt中不能用C++进行开发,那就有点大失所望了。 接下来将与大家一起来尝试写一个C++程序,并把它做成 ipk 包,并试运行。 各文件内容 在 SDK/package/ 路径下创建...

临峰不畏
2015/05/07
0
9
[c/c++奇技淫巧]不用循环判断输出5到1

偶尔看到的一道题,和哥们几个讨论了一下,这玩意,不是循环就是递归了么,当然,只要达到目的,管他什么循环递归,对吧。现在总结一下我们能想到的所有的方法,大家有新的想法欢迎跟帖讨论~...

-水水-
2014/10/08
0
7

没有更多内容

加载失败,请刷新页面

加载更多

React 服务器渲染原理解析与实践

网盘下载地址 React 服务器渲染原理解析与实践 本套课程,讲解了React中SSR技术的整个搭建思路及流程,完整的从原理上讲清楚了SSR的概念,重点在于讲解编写SSR框架遇到的各种知识点,以及细节...

qq__2304636824
19分钟前
0
0
sourcetree 离线免注册登录安装教程

Sourcetree是一个优秀的git可视化管理工具,深受开发者喜爱Sourcetree官网,但是在安装时需要谷歌账户登录,需要翻qiang才可以,此一点一直被人们所诟病。今天本教程就为大家提供离线免登陆安...

QQZZFT
47分钟前
1
0
使用 PostgreSQL 解决一个实际的统计分析问题

使用 PostgreSQL 解决一个实际的统计分析问题作者:老农民(刘启华)Email: 46715422@qq.com 之前有个朋友扔给我一个奇葩需求,他们公司之前做了一批问卷调查,全部都是统一格式的excel...

新疆老农民
50分钟前
5
0
TypeScript基础入门之高级类型的映射类型

转发 TypeScript基础入门之高级类型的映射类型 高级类型 映射类型 一个常见的任务是将一个已知的类型每个属性都变为可选的: interface PersonPartial {    name?: string;    age?...

durban
今天
1
0
Dubbo源码分析(6):Dubbo内核实现之基于SPI思想Dubbo内核实现

SPI接口定义 定义了@SPI注解 package com.alibaba.dubbo.common.extension; import java.lang.annotation.Documented;import java.lang.annotation.ElementType;import java.lang.an......

郑加威
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部