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;
}

相关文章
|
4月前
【每日一题Day244】LCP 41. 黑白翻转棋 bfs dfs
【每日一题Day244】LCP 41. 黑白翻转棋 bfs dfs
32 0
|
3月前
|
算法 Java C++
走迷宫(BFS)
走迷宫(BFS)
26 0
|
4月前
|
存储 人工智能 BI
【每日一题Day216】LC1377 T 秒后青蛙的位置 | BFS DFS
【每日一题Day216】LC1377 T 秒后青蛙的位置 | BFS DFS
28 0
|
7月前
Dungeon Master(BFS广度优先搜索)
Dungeon Master(BFS广度优先搜索)
25 0
|
8月前
UVa11710 - Expensive subway(最小生成树)
UVa11710 - Expensive subway(最小生成树)
27 0
|
人工智能 算法 BI
LeetCode 周赛 341 场,模拟 / 树上差分 / Tarjan 离线 LCA / DFS
上周末有单双周赛,双周赛我们讲过了,单周赛那天早上有事没参加,后面做了虚拟竞赛,然后整个人就不好了。前 3 题非常简单,但第 4 题有点东西啊,差点就放弃了。最后,被折磨了一个下午和一个大夜总算把第 4 题做出来了,除了新学的 Tarjon 离线算法,这道题还涉及到树上差分、前缀和、DFS、图论等基础知识,几度被折磨得想要放弃。这种感觉,似乎和当年在 LeetCode 上做前 10 题的时候差不多哈哈。
66 0
POJ-2251,Dungeon Master(三维迷宫BFS)
POJ-2251,Dungeon Master(三维迷宫BFS)
|
存储 定位技术 C++
【PTA】龙舌兰酒吧 (BFS求双源最短路)
【PTA】龙舌兰酒吧 (BFS求双源最短路)
128 0
【PTA】龙舌兰酒吧 (BFS求双源最短路)