本文主要是介绍Dungeon Master -uva,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一个简答的三维BFS遍历,我从中领悟到了惨痛的教训,关于栈的溢出!!!
不多说了。。郁闷
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_SIZE 50 + 10
int Dung[MAX_SIZE][MAX_SIZE][MAX_SIZE];
int time[MAX_SIZE][MAX_SIZE][MAX_SIZE]={0};
char Dungs[MAX_SIZE][MAX_SIZE][MAX_SIZE];
int L,R,C;
int x1,y1,z1,x2,y2,z2;
/*储存开始和结束的坐标*/
/*三维分别代表层数,以及该层的坐标(x,y)*/
void get_array(int Dung[][MAX_SIZE][MAX_SIZE])/*建立迷宫*/
{int i,j,k;char z;for(i=0;i<L;i++)for(j=0;j<R;j++)scanf("%s",Dungs[i][j]);for(i=0;i<L;i++){for(j=0;j<R;j++){for(k=0;k<C;k++){z=Dungs[i][j][k];if(z=='S'){Dung[i][j][k]=1;/*如果是入口的话记录*/x1=i;y1=j;z1=k;}else if(z=='E'){Dung[i][j][k]=1;/*记录出口的坐标*/x2=i;y2=j;z2=k;}else if(z=='.')Dung[i][j][k]=1;else if(z=='#')Dung[i][j][k]=0;}}}/*for(i=0;i<L;i++){for(j=0;j<R;j++){for(k=0;k<C;k++)printf("%d",Dung[i][j][k]);printf("\n");}printf("\n");}*/}
int bfs(int x,int y,int z)/*开始进行遍历*/
{int xx[100000],yy[100000],zz[100000];/*用来储存点的坐标*/int nx,ny,nz;int front=0,back=0,d;int dx[]={1,-1,0,0,0,0};int dy[]={0,0,1,-1,0,0};int dz[]={0,0,0,0,1,-1};int vis[MAX_SIZE][MAX_SIZE][MAX_SIZE]={0};xx[back]=x;yy[back]=y;zz[back]=z;vis[x][y][z]=1;/*将其实点记录为已经遍历过的点*/back++;while(front<back){x=xx[front];y=yy[front];z=zz[front];front++;/*可以走6个方向,上下左右前后*/for(d=0;d<6;d++){nx=x+dx[d];ny=y+dy[d];nz=z+dz[d];/*可以走6个方向*/if(nx>=0&&ny>=0&&nz>=0&&nx<L&&ny<R&&nz<C&&vis[nx][ny][nz]==0&&Dung[nx][ny][nz]==1){/*如果在迷宫的范围内,并且没用被访问过,并且不是死路*/vis[nx][ny][nz]=1;/*标记为访问过了*/time[nx][ny][nz]=time[x][y][z]+1;if(nx==x2&&ny==y2&&nz==z2)return 1;xx[back]=nx;yy[back]=ny;zz[back]=nz;back++;}}}return 0;
}
int main()
{int i,j,k;for(;scanf("%d%d%d",&L,&R,&C);){getchar();if(!L&&!R&&!C) break;get_array(Dung);/*建立三维迷宫*//* printf("(%d,%d,%d) (%d,%d,%d)\n",x1,y1,z1,x2,y2,z2);*/bfs(x1,y1,z1);/*从入口处开始进行BFS遍历*/if(bfs(x1,y1,z1))printf("Escaped in %d minute(s).\n",time[x2][y2][z2]);elseprintf("Trapped!\n");memset(Dung,0,sizeof(Dung));memset(time,0,sizeof(time));memset(Dungs,0,sizeof(Dungs));}return 0;
}
这篇关于Dungeon Master -uva的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!