zoj 1940 || poj 2251 Dungeon Master(bfs)

时间:2022-07-16 16:22:17

题意:


在三维空间里,从S走到E,‘.' 是路,‘#'是rock.


分析:

三维空间 6个方向bfs ,本来应该秒杀的题目,无奈啊,1输入的时候因为换行符处理的恶心,后来干脆用C++的Cin流,省力多了。

2.SF 多次,后来火了、,把init部分改成了memset,AC 了,悲剧啊,图截下来问别人才发现数组越界初始化了。>_<

i<35写成了i<=35.就这样的我的时间浪费在了这里。

 

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
typedef struct po{
	int x,y,z;
	int min;
}point;
queue<point>Q;
int L,R,C;
char a[35][35][35];
int map[35][35][35];
int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int sx,sy,sz,ey,ex,ez,min;
point E;
void BFS(point S)
{
	int i,ff=1,x,y,z;
	S.min=0;
	map[S.x][S.y][S.z]=1;
	Q.push(S);
	point head,temp;
	while(!Q.empty ())
	{
		head=Q.front ();
		if(head.x==E.x&&head.y==E.y&&head.z==E.z)
			{ff=0;printf("Escaped in %d minute(s).\n",head.min);break;}
		Q.pop ();
		for(i=0;i<6;i++)
		{
			x=head.x+dir[i][0];
			y=head.y+dir[i][1];
			z=head.z+dir[i][2];
			if(x>=0&&x<L&&y >=0&&y<R&&z>=0 && z<C&&map[x][y][z]==0&&a[x][y][z]!='#')
			{
				map[x][y][z]=1;
				temp.x=x;
				temp.y=y;
				temp.z =z;
				temp.min =head.min+1;
				Q.push(temp);
			}
		}
	}
	if(ff==1) printf("Trapped!\n");
}
int main()
{
	int i,j,k;
	point S;
	while(scanf("%d%d%d",&L,&R,&C)!=EOF)
	{
		
		if(L==0&&R==0&&C==0) break;
		while(!Q.empty ()) Q.pop();
		for(i=0;i<35;i++)
			for(j=0;j<35;j++)
				for(k=0;k<35;k++)
					map[i][j][k]=0;
		for(i=0;i<L;i++)
		{
			for(j=0;j<R;j++)
			{
				for(k=0;k<C;k++)
				{
					cin>>a[i][j][k];
					if(a[i][j][k]=='S') {S.x=i;S.y=j;S.z=k;}
					if(a[i][j][k]=='E') {E.x=i;E.y=j;E.z=k;}
				}
			}
		}
		BFS(S);
	}
	return 0;
}