Uva 532 Dungeon Master

题目：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=473

这道题也是一道很基础的bfs，仅仅是图从二维变成三维
在入队列之前进行判断比出队列之后再进行判断会节约运行的时间，因为减少了入队、出队的赋值操作，对于bfs这样低效的算法，在某些题目里面是很容易超时的，所以能够节约点时间还是好的
还有一点就是自己手写的队列要比调用STL的队列要快一些，但是提高了编程复杂度

#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 30+10
using namespace std;

struct Point
{
	int x,y,z,step;
};

char mat[MAXN][MAXN][MAXN];
char vis[MAXN][MAXN][MAXN];

int bfs(Point start)
{
	vis[start.z][start.x][start.y]=1;
	queue<Point> q;
	q.push(start);
	while(!q.empty())
	{
		Point cur=q.front();
		q.pop();
		int dir[8][3]={-1,0,0,1,0,0,0,-1,0,0,1,0,0,0,-1,0,0,1};
		for(int i=0;i<8;i++)
		{
			Point next;
			next.z=cur.z+dir[i][0];
			next.x=cur.x+dir[i][1];
			next.y=cur.y+dir[i][2];
			next.step=cur.step+1;					
			if(!vis[next.z][next.x][next.y]&&mat[next.z][next.x][next.y]!='#')
			{
				if(mat[next.z][next.x][next.y]=='E') 
					return next.step;
				vis[next.z][next.x][next.y]=1;
				q.push(next);
			}
		}
	}
	return -1;//-1代表无法到达
}
void init()//初始化，全部设为墙壁
{
	memset(vis,0,sizeof(vis));
	for(int i=0;i<MAXN;i++)
		for(int j=0;j<MAXN;j++)
			for(int k=0;k<MAXN;k++)
				mat[i][j][k]='#';
}
int main()
{
	int L,R,C;
	Point start;
	while(cin>>L>>R>>C&&L&&R&&C)
	{
		init();
		for(int i=1;i<=L;i++)//之所以从1开始，是因为外面增加一层墙壁可以省去越界的判断
			for(int j=1;j<=R;j++)
				for(int k=1;k<=C;k++)
				{
					cin>>mat[i][j][k];
					if(mat[i][j][k]=='S')
					{
						start.z=i;
						start.x=j;
						start.y=k;
						start.step=0;
					}
				}
		int ans=bfs(start);
		if(ans==-1) cout<<"Trapped!"<<endl;
		else cout<<"Escaped in "<<ans<<" minute(s)."<<endl;
	}
	return 0;
}