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

相关文章
|
7月前
|
Java
hdu-1874-畅通工程续(dijkstra + SPFA )
hdu-1874-畅通工程续(dijkstra + SPFA )
45 0
Dungeon Master(BFS广度优先搜索)
Dungeon Master(BFS广度优先搜索)
44 0
|
机器学习/深度学习 测试技术
UVA11175 有向图D和E From D to E and Back
UVA11175 有向图D和E From D to E and Back
UVA11175 有向图D和E From D to E and Back
AtCoder Beginner Contest 216 D - Pair of Balls (思维建图 拓扑排序判断有向图是否有环)
AtCoder Beginner Contest 216 D - Pair of Balls (思维建图 拓扑排序判断有向图是否有环)
127 0
codeforces1253——D. Harmonious Graph(并查集)
codeforces1253——D. Harmonious Graph(并查集)
96 0
[Nowcoder] network | Tarjan 边双连通分量 | 缩点 | LCA倍增优化 | 并查集
题目描述 A network administrator manages a large network. The network consists of N computers and M links between pairs of computers. Any pair of computers are connected directly or indirectly by successive links, so data can be transformed between any two computers.
127 0
[Nowcoder] network | Tarjan 边双连通分量 | 缩点 | LCA倍增优化 | 并查集
POJ-2251,Dungeon Master(三维迷宫BFS)
POJ-2251,Dungeon Master(三维迷宫BFS)
HDU-1874,畅通工程续(Floyd最短路)
HDU-1874,畅通工程续(Floyd最短路)

热门文章

最新文章