UVa532 - Dungeon Master

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <string>
#include <deque>
#include <vector>
#include <cstring>
using namespace std;
const int maxsize = 40;
int visited[maxsize][maxsize][maxsize];
string s[maxsize][maxsize];
int num[maxsize][maxsize][maxsize];
int L,R,C;
int d[6][3]={
	0,0,-1,
	0,0,1,
	0,1,0,
	0,-1,0,
	1,0,0,
	-1,0,0
			};
struct Point
{
	int x,y,z;
	Point(int x,int y,int z)
	{
		this->x=x;
		this->y=y;
		this->z=z;
	}
	Point(const Point &p)
	{
		this->x=p.x;
		this->y=p.y;
		this->z=p.z;
	}
};
bool BFS(int start_L,int start_R,int start_C,int end_L,int end_R,int end_C)
{
	deque<Point> dvi;
	Point p(start_L,start_R,start_C);
	dvi.push_back(p);
	visited[start_L][start_R][start_C]=1;
	while(!dvi.empty()&&(dvi.front().x!=end_L||dvi.front().y!=end_R||dvi.front().z!=end_C))
	{
		p=dvi.front();
		dvi.pop_front();
		for(int i=0;i<6;++i)
		{
			int x=p.x+d[i][0];
			int y=p.y+d[i][1];
			int z=p.z+d[i][2];
			if(x>=0&&x<L&&y>=0&&y<R&&z>=0&&z<C&&!visited[x][y][z]&&s[x][y][z]!='#')
			{
				num[x][y][z]=num[p.x][p.y][p.z]+1;
				visited[x][y][z]=1;
				Point q(x,y,z);
				dvi.push_back(q);
			}
		}
	}
	if(!dvi.empty())
		return true;
	else
		return false;
}
int main()
{
	while(cin>>L>>R>>C&&(L||R||C))
	{
		int i,j,k;
		int start_L,start_R,start_C;
		int end_L,end_R,end_C;
		for(i=0;i<L;++i)
		{
			for(j=0;j<R;++j)
			{
				cin>>s[i][j];
				for(k=0;k<s[i][j].size();++k)
				{
					if(s[i][j][k]=='S')
					{
						start_L=i;
						start_R=j;
						start_C=k;
						break;
					}
					else
					{
						if(s[i][j][k]=='E')
						{
							end_L=i;
							end_R=j;
							end_C=k;
							break;
						}
					}
				}
			}
		}
		memset(visited,0,sizeof(visited));
		memset(num,0,sizeof(num));
		if(BFS(start_L,start_R,start_C,end_L,end_R,end_C))
			cout<<"Escaped in "<<num[end_L][end_R][end_C]<<" minute(s)."<<endl;
		else
			cout<<"Trapped!"<<endl;
	}
	return 0;
}