Dungeon Master(bfs)逃离迷宫 POJ - 2251

时间:2022-06-25 19:18:29

题目大意:有一个三维迷宫,起始点为S,终点为E,需要判断从S点能不能走到E点,如果可以输出最短时间,如果不行,输出Trapped!

 思路:从S点开始bfs 与一般bfs不同的是有六个方向可以走,bfs道E点输出时间,不行输出Trapped!即可刚开始学搜索,第一次用dfs直接tle dfs就AC了


#include<stdio.h>
#include<string.h>
int x,y,z;
int x_s,y_s,z_s,x_e,y_e,z_e;
char map[40][40][40];//存迷宫
int book[40][40][40];//标记是否走过
int s[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,-1},{0,0,1}};//六个方向
struct node{
	int x;
	int y;
	int z;
	int step;
}queue[30000];//开队列  用来bfs存步数
int check(int x_c,int y_c,int z_c){//判断这个点是否可以走
	if(x_c>=0&&x_c<x&&y_c>=0&&y_c<y&&z_c>=0&&z_c<z&&book[x_c][y_c][z_c]==0&&map[x_c][y_c][z_c]!='#')
	return 1;
	return 0;
}
void bfs();
int main(void)
{
	while(scanf("%d%d%d",&x,&y,&z),x&&y&&z){
		int i,j,k;
		for(i=0;i<x;i++){
			getchar();
			for(j=0;j<y;j++){
				memset(book[i][j],0,31);
				for(k=0;k<z;k++){
					scanf("%c",&map[i][j][k]);
					if(map[i][j][k]=='S'){
						x_s=i;y_s=j;z_s=k;//起点
					}
					if(map[i][j][k]=='E'){
						x_e=i;y_e=j;z_e=k;//终点
					}
				}
				getchar();
			}
		}
		memset(book,0,sizeof(book));
		bfs( );
	}
	return 0;
 } 
 void  bfs(){
 	struct node temp;
 	book[x_s][y_s][z_s]=1;
 	int head=0;
	int tail=1;
	queue[head].x=temp.x=x_s;
	queue[head].y=temp.y=y_s;
	queue[head].z=temp.z=z_s;
	queue[head].step=0;
 	while(head<tail){
 	int i;
	if(queue[head].x==x_e&&queue[head].y==y_e&&queue[head].z==z_e){//判断是否到达终点
 		printf("Escaped in %d minute(s).\n",queue[head].step);
 		return ;
 	}
	for(i=0;i<6;i++){//走六个方向
	 	 temp.x=queue[head].x+s[i][0];
	 	 temp.y=queue[head].y+s[i][1];
	 	 temp.z=queue[head].z+s[i][2];
	 	if(check(temp.x,temp.y,temp.z)){
	 		book[temp.x][temp.y][temp.z]=1;
	 		queue[tail].x=temp.x;
	 		queue[tail].y=temp.y;
	 		queue[tail].z=temp.z;
	 		queue[tail].step=queue[head].step+1;
	 		tail++;
       	}
       
    }	head++;
	}
	printf("Trapped!\n");//如果用bfs没找到,输出trapped!
 }