zoj 1940 Dungeon Master

zoj 1940 Dungeon Master

/*
三维广搜
*/
#define LOCAL
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iomanip>
#include<string>
#include<algorithm>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#define N 30
using namespace std;
class POSITION 
{public:int x,y,z;};
int map[N+5][N+5][N+5],l,r,c,dir[6][3]={0,0,1,0,0,-1,0,1,0,0,-1,0,1,0,0,-1,0,0};
bool legal(POSITION po)
{if(po.x>=1&&po.x<=l&&po.y>=1&&po.y<=r&&po.z>=1&&po.z<=c) return true;return false;}
int main()
{
#ifdef LOCAL
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
#endif
 
	   int ex,ey,ez,i,j,k;POSITION po,pos;char ch;
	   while(cin>>l>>r>>c&&l)
	   {
		   memset(map,-1,sizeof(map));
		   queue<POSITION>q;
			for(i=1;i<=l;i++)
			{
				for(j=1;j<=r;j++)
				{
					for(k=1;k<=c;k++)
					{
						cin>>ch;
						if(ch=='#') map[i][j][k]=1;
						else if(ch=='S'){pos.x=i;pos.y=j;pos.z=k;map[i][j][k]=0;q.push(pos);}
						else if(ch=='E'){ex=i;ey=j;ez=k;}
					}
				}
			}
			while(!q.empty())
			{
				po=q.front();q.pop();
				for(i=0;i<6;i++)
				{
					pos.x=po.x+dir[i][0];pos.y=po.y+dir[i][1];pos.z=po.z+dir[i][2];
					if(legal(pos)&&map[pos.x][pos.y][pos.z]==-1){map[pos.x][pos.y][pos.z]=map[po.x][po.y][po.z]+1;q.push(pos);}
				}
			}
			if(map[ex][ey][ez]!=-1)cout<<"Escaped in "<<map[ex][ey][ez]<<" minute(s)."<<endl;
			else cout<<"Trapped!"<<endl;
	   }
		return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注