Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- USER: Raqibul Islam
- TASK: contest(5-6-10) - Dungeon Master
- ALGO: 3d-bfs
- STAT:
- */
- #include <iostream>
- #include <sstream>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <cctype>
- #include <cstring>
- #include <string>
- #include <algorithm>
- #include <vector>
- #include <map>
- #include <set>
- #include <list>
- #include <queue>
- #include <stack>
- using namespace std;
- #define READ(x) freopen(x,"r",stdin);
- #define WRITE(x) freopen(x,"w",stdout);
- #define EPS 1e-10
- #define SET(x) memset(x,-1,sizeof(x))
- #define CLR(x) memset(x,0,sizeof(x))
- #define pii pair<int,int>
- #define vi vector<int>
- #define i64 __int64
- #define _max(a,b) ((a)>(b)?(a):(b))
- #define _min(a,b) ((a)<(b)?(a):(b))
- #define _abs(x) ((x)<0?-(x):(x))
- #define sq(x) ((x)*(x))
- #define sz(x) x.size()
- #define MAX 35
- #define INF 1<<24
- int L, R, C;
- struct node{
- int level, row, col;
- int color, dist;
- char ch;
- } graph[MAX][MAX][MAX];
- queue <node> Q;
- void init_graph()
- {
- int i, j, k;
- for(i=0; i<MAX; i++)
- for(j=0; j<MAX; j++)
- for(k=0; k<MAX; k++)
- {
- graph[i][j][k].level = i;
- graph[i][j][k].row = j;
- graph[i][j][k].col = k;
- graph[i][j][k].color = 0;
- graph[i][j][k].dist = INF;
- graph[i][j][k].ch = '#';
- }
- }
- void run_bfs()
- {
- int tmp_level, tmp_row, tmp_col;
- graph[Q.front().level][Q.front().row][Q.front().col].color = 2;
- tmp_level = Q.front().level;
- tmp_row = Q.front().row - 1;
- tmp_col = Q.front().col;
- if(tmp_row>0 && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
- {
- graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
- graph[tmp_level][tmp_row][tmp_col].color = 1;
- Q.push(graph[tmp_level][tmp_row][tmp_col]);
- }
- tmp_level = Q.front().level;
- tmp_row = Q.front().row + 1;
- tmp_col = Q.front().col;
- if(tmp_row<=R && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
- {
- graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
- graph[tmp_level][tmp_row][tmp_col].color = 1;
- Q.push(graph[tmp_level][tmp_row][tmp_col]);
- }
- tmp_level = Q.front().level;
- tmp_row = Q.front().row;
- tmp_col = Q.front().col - 1;
- if(tmp_col>0 && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
- {
- graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
- graph[tmp_level][tmp_row][tmp_col].color = 1;
- Q.push(graph[tmp_level][tmp_row][tmp_col]);
- }
- tmp_level = Q.front().level;
- tmp_row = Q.front().row;
- tmp_col = Q.front().col + 1;
- if(tmp_col<=C && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
- {
- graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
- graph[tmp_level][tmp_row][tmp_col].color = 1;
- Q.push(graph[tmp_level][tmp_row][tmp_col]);
- }
- tmp_level = Q.front().level - 1;
- tmp_row = Q.front().row;
- tmp_col = Q.front().col;
- if(tmp_level>0 && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
- {
- graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
- graph[tmp_level][tmp_row][tmp_col].color = 1;
- Q.push(graph[tmp_level][tmp_row][tmp_col]);
- }
- tmp_level = Q.front().level + 1;
- tmp_row = Q.front().row;
- tmp_col = Q.front().col;
- if(tmp_level<=L && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
- {
- graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
- graph[tmp_level][tmp_row][tmp_col].color = 1;
- Q.push(graph[tmp_level][tmp_row][tmp_col]);
- }
- Q.pop();
- }
- int main()
- {
- int i, j, k;
- while(scanf("%d %d %d", &L, &R, &C)==3)
- {
- if(L==0 && R==0 && C==0)
- break;
- init_graph();
- for(i=1; i<=L; i++)
- for(j=1; j<=R; j++)
- for(k=1; k<=C; k++)
- cin >> graph[i][j][k].ch;
- /*for(i=1; i<=L; i++)
- for(j=1; j<=R; j++)
- {
- for(k=1; k<=C; k++)
- {
- printf("%c", graph[i][j][k].ch);
- }
- printf("\n");
- }
- */
- for(i=1; i<=L; i++)
- for(j=1; j<=R; j++)
- for(k=1; k<=C; k++)
- {
- if(graph[i][j][k].ch == 'S')
- {
- graph[i][j][k].dist = 0;
- Q.push(graph[i][j][k]);
- break;
- }
- }
- while(!Q.empty())
- {
- if(graph[Q.front().level][Q.front().row][Q.front().col].color != 2)
- run_bfs();
- }
- /*for(i=1; i<=L; i++)
- for(j=1; j<=R; j++)
- {
- for(k=1; k<=C; k++)
- {
- printf("%c", graph[i][j][k].ch);
- }
- printf("\n");
- }
- */
- int flag = 0;
- int end_level, end_row, end_col;
- for(i=1; i<=L; i++)
- for(j=1; j<=R; j++)
- for(k=1; k<=C; k++)
- {
- if(graph[i][j][k].ch=='E' && graph[i][j][k].dist<INF)
- {
- end_level = i;
- end_row = j;
- end_col = k;
- flag = 1;
- break;
- }
- }
- if(flag) printf ("Escaped in %d minute(s).\n", graph[end_level][end_row][end_col].dist);
- else printf("Trapped!\n");
- }
- //system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement