POJ 2251 Dungeon Master【BFS】

题意：给出一个三维坐标的牢，给出起点st,给出终点en,问能够在多少秒内逃出。

学习的第一题三维的广搜@_@

过程和二维的一样，只是搜索方向可以有6个方向(x,y,z的正半轴，负半轴)

另外这一题的输入的方式还要再多看看--@_@--

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm> 
#include<queue>
#define maxn 55 
using namespace std;
int map[maxn][maxn][maxn],vis[maxn][maxn][maxn];
int dir[6][3]={{0,0,1},{0,0,-1},{1,0,0},{-1,0,0},{0,1,0},{0,-1,0}};
int l,r,c,flag;
char str[10005];
struct node
{
	int x,y,z;
	int step;
} st,en;
queue<node> q;
void bfs(int x,int y,int z)
{  
	node now,next;
	while(!q.empty()) q.pop();//调用前清空队列 
	now.x=x;now.y=y;now.z=z;now.step=0;
	q.push(now);
	vis[x][y][z]=1;
	while(!q.empty())
	{
		now=q.front();q.pop();	
		for(int i=0;i<6;i++)
		{
			next.x=now.x+dir[i][0];
			next.y=now.y+dir[i][1];
			next.z=now.z+dir[i][2];
			if(map[next.x][next.y][next.z]&&!vis[next.x][next.y][next.z])
			{				
				vis[next.x][next.y][next.z]=1;
				next.step=now.step+1;//步数加1之后再如队列，因为 搞反 这个wa了好几次 
				q.push(next);
				if(next.x==en.x&&next.y==en.y&&next.z==en.z)
				{
					flag=1;
					en.step=next.step;
					return;
				}
			}			
		}
	}
	return;
}
int main()
{
	char ch;
	int i,j,k;
	while(scanf("%d %d %d",&l,&r,&c)!=EOF&&l&&r&&c)
	{
		flag=0;
		memset(map,0,sizeof(map));
		memset(vis,0,sizeof(vis));
	
		gets(str);
		for(i=1;i<=l;i++)
		{
			for(j=1;j<=r;j++)
			{
				for(k=1;k<=c;k++)
				{
					scanf("%c",&ch);
					if(ch=='S') {st.x=i;st.y=j;st.z=k;}
					if(ch=='E'){en.x=i;en.y=j;en.z=k;}
					if(ch!='#') map[i][j][k]=1;//map数组 相当于限定是否出界 
				}
				gets(str);				
			}
			gets(str);
		}
		bfs(st.x,st.y,st.z);
		if(flag) printf("Escaped in %d minute(s).
",en.step);
		else printf("Trapped!
");
	}	
}

　　go---go-----===