UVA532-Dungeon Master(三维迷宫BFS)

简介: UVA532-Dungeon Master(三维迷宫BFS)

样例输入:


3 4 5


S....


.###.


.##..


###.#


#####


#####


##.##


##...


#####


#####


#.###


####E


1 3 3


S##


#E#


###


0 0 0


样例输出:


Escaped in 11 minute(s).


Trapped!


AC Code:


#include<stdio.h>//写万能头写多了,不妨再熟悉一下C语言的头文件吧!!! 
#include<string.h>
#include<stdlib.h>
#define N 500
char s[N][N][N];//存入地图 
bool vis[N][N][N];//标记数组  
int l,r,c,head,tail,x1,y1,z1,x2,y2,z2,flag;
int dx[]={-1,1,0,0,0,0};//三维迷宫,需要三个方向数组 
int dy[]={0,0,0,0,-1,1};
int dz[]={0,0,1,-1,0,0};
struct node {
  int x,y,z,step;
}q[N*N];//模拟队列 
bool judge(int x,int y,int z) {
  //不越界,并且这个点没有走过 
  if(x>=0&&x<l&&y>=0&&y<r&&z>=0&&z<c&&vis[x][y][z]==false) {
    return true;
  }
  return false;
}
int bfs(int x1,int y1,int z1,int x2,int y2,int z2) {
  head=tail=1;//队头队尾初始化 
  q[head].x=x1;//起点入队 
  q[head].y=y1;
  q[head].z=z1;
  q[head].step=0;//此时处于起点,移动次数为0
  tail++;//起点入队之后,队尾向后移动一格 
  vis[x1][y1][z1]=true;//标记起点已经走过 
  while(head<tail) {//队列不为空 
    for(int i=0;i<6;i++) {//六个方向搜索 
      int tx=q[head].x+dx[i];
      int ty=q[head].y+dy[i];
      int tz=q[head].z+dz[i];
      if(judge(tx,ty,tz)) {//合法判断 
        vis[tx][ty][tz]=true;//标记该点 
        q[tail].x=tx;//该点入队 
        q[tail].y=ty;
        q[tail].z=tz;
        q[tail].step=q[head].step+1;//移动次数+1 
        if(tx==x2&&ty==y2&&tz==z2) {//走到终点 
          //队尾此时向后移动了一格,所以移动次数应该是队尾回退一格的次数 
          return q[tail].step;
        }
        tail++;//新的点入队,队尾向后移动一格 
      }
    }
    head++;//队头向后移动,继续搜索下一个点 
  }
  return -1;//走不到终点 
}
int main() {
  while(~scanf("%d %d %d",&l,&r,&c)) {
    if(!l&&!r&&!c) {//结束标志为三个0 
      break;
    }
    memset(vis,false,sizeof(vis));//清空标记数组 
    for(int i=0;i<l;i++) {
      for(int j=0;j<r;j++) {
        for(int k=0;k<c;k++) {
          scanf(" %c",&s[i][j][k]);
          if(s[i][j][k]=='S') {//记录起点 
            x1=i;
            y1=j;
            z1=k;
          }else if(s[i][j][k]=='E') {//记录终点 
            x2=i;
            y2=j;
            z2=k;
          }else if(s[i][j][k]=='#') {//将障碍物直接标记为true,意味着不能走 
            vis[i][j][k]=true;
          }
        }
      }
    }
    int flag=bfs(x1,y1,z1,x2,y2,z2);//开始搜索 
    if(flag==-1) {//无法到达 
      printf("Trapped!\n");
    }else {//可以到达 
      printf("Escaped in %d minute(s).\n",flag);
    }
  }
  return 0;
}

相关文章
|
小程序 JavaScript 数据库
小程序解析富文本html内容
小程序解析富文本html内容
171 0
|
安全 关系型数据库 MySQL
MySQL8 中文参考(二十七)(1)
MySQL8 中文参考(二十七)
186 1
|
存储 安全 Java
Java修仙之路,十万字吐血整理全网最完整Java学习笔记(基础篇)
从Java环境的搭建到实际代码的编写,从基本用法的讲解到底层原理的剖析,深度解析Java基础知识。本文是《Java学习路线》专栏的起始文章,旨在提供一套完整的Java学习路线,覆盖Java基础知识、数据库、SSM/SpringBoot等框架、Redis/MQ等中间件、设计模式、架构设计、性能调优、源码解读、核心面试题等全面的知识点,并在未来不断更新和完善,帮助Java从业者在更短的时间内成长为高级开发。
Java修仙之路,十万字吐血整理全网最完整Java学习笔记(基础篇)
|
前端开发 容器
CSS 弹性布局,大厂意外流出
CSS 弹性布局,大厂意外流出
|
人工智能 API 数据安全/隐私保护
|
搜索推荐
Boom3D软件2023最新版本有哪些新功能特色?
为了更好地感受音乐的魅力,Boom 3D 可以让你对音效进行个性化增强,并集成 3D 环绕立体声效果,可以让你在使用任何耳机时,都拥有纯正、优质的音乐体验。Boom 3D是一款充满神奇魅力的3D环绕音效升级版,BOOM 3D是一个全新的专业音频应用程序,提供丰富和强烈的音频与3D环绕声音,让耳机的声音更好!文件大小为40.65 MB,适用系统为WinXP/Win7/Win10/Win All,以下为介绍或使用方法。
569 2
|
索引
带你读《Elastic Stack 实战手册》之23:——3.4.2.8.Index template(1)
带你读《Elastic Stack 实战手册》之23:——3.4.2.8.Index template(1)
144 0
内存越界并不等于马上出错
内存越界并不等于马上出错
156 0
|
机器学习/深度学习 数据采集 人工智能
AI平台-AutoML-2019年几个靠谱的AutoML框架
AutoML,也称自动机器学习,是指将机器学习应用于现实问题的端到端过程自动化的过程。
4255 0
|
前端开发
Bootstrap系列 -- 5. 文本对齐方式
一. 文本对齐样式   .text-left:左对齐   .text-center:居中对齐   .text-right:右对齐   .text-justify:两端对齐   二. 使用方式 我居左 我居中 我居右 这个强调动手、项目主导的合作项目将首先提供科技方面的硕士学位,过几年会提供其他学位。
1367 0