样例输入:
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; }