damihenrique

Untitled

Jul 10th, 2014
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.83 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <stdio.h>
  4. #include <cstring>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <utility>
  8. #include <queue>
  9. #include <map>
  10. #include <stack>
  11. #include <cmath>
  12. #include <set>
  13.  
  14. #define INF 99999999
  15. #define rep(i, a, b) for (int i = int(a); i < int(b); i++)
  16. #define TRvii(c, it) for (vii::iterator it = (c).begin(); it != (c).end(); it++)
  17. #define tr(it, s)  for ( typeof ( s.begin( ) ) it=s.begin( ); it!=s.end( ); it++ )
  18. #define pb push_back
  19. #define clr(a) memset((a),0,sizeof(a))
  20. #define pi 3.1415926535897932384626433832795028841971
  21.  
  22. using namespace std;
  23.  
  24. typedef long long ll;
  25. typedef pair < int, int >  ii;
  26. typedef vector < int >  vi;
  27. typedef vector < ii >  vii;
  28.  
  29. int n, l, c, px, py, pz, fx, fy, fz;
  30. char m[32][32][32];
  31. bool vis[32][32][32];
  32.  
  33. int dx[] = {0, 0, 0, 0, 1, -1};
  34. int dy[] = {0, 0, 1, -1, 0, 0};
  35. int dz[] = {1, -1, 0, 0, 0, 0};
  36.  
  37. struct ponto{
  38.      
  39.      int x, y, z;    
  40.      
  41. };
  42.  
  43.  
  44. bool dentro(int x, int y, int z){
  45.      
  46.      return(x>=0 && y>=0 && z>=0 && x<n && y<l && z<c);
  47.      
  48. }
  49.  
  50.  
  51. int bfs(int x, int y, int z){
  52.      
  53.      memset(vis,false,sizeof(vis));
  54.      queue<pair<int,ponto> > q;
  55.      ponto p;
  56.      
  57.      p.x = x; p.y = y; p.z = z;
  58.      
  59.      q.push(make_pair(0,p));
  60.      vis[x][y][z] = true;
  61.      
  62.      while(!q.empty()){
  63.          
  64.           ponto pp = q.front().second;
  65.           int mov = q.front().first;
  66.           q.pop();
  67.          
  68.           rep(i,0,6){
  69.                
  70.                int nx = pp.x + dx[i];
  71.                int ny = pp.y + dy[i];
  72.                int nz = pp.z + dz[i];
  73.                
  74.                if(dentro(nx,ny,nz) && !vis[nx][ny][nz] && m[nx][ny][nz] != '#'){      
  75.  
  76.                     ponto ppp;
  77.                    
  78.                     vis[nx][ny][nz] = true;
  79.                     ppp.x = nx; ppp.y = ny; ppp.z = nz;
  80.                     q.push(make_pair(mov+1,ppp));
  81.                    
  82.                     if(m[nx][ny][nz] == 'E')
  83.                          return mov+1;        
  84.                }  
  85.           }    
  86.          
  87.      }
  88.      
  89.      return INF;
  90. }
  91.  
  92.  
  93. int main(){
  94.      
  95.      char branco[10];
  96.      
  97.      while(scanf("%d%d%d",&n,&l,&c) && n+l+c){
  98.          
  99.           getchar();
  100.           rep(i,0,n){
  101.                
  102.                rep(j,0,l)
  103.                    rep(k,0,c){
  104.                        scanf(" %c",&m[i][j][k]);
  105.                        if(m[i][j][k] == 'S'){
  106.                            px = i; py = j; pz = k;      
  107.                        }
  108.                    }
  109.                
  110.                gets(branco);  
  111.           }
  112.          
  113.          
  114.           int ans = bfs(px, py, pz);  
  115.          
  116.           if(ans == INF)
  117.                printf("Trapped!\n");
  118.           else
  119.                printf("Escaped in %d minute(s).\n",ans);
  120.      }
  121.      
  122.  
  123.      return 0;
  124. }
Advertisement
Add Comment
Please, Sign In to add comment