Advertisement
Guest User

Untitled

a guest
May 29th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.16 KB | None | 0 0
  1. /*
  2. USER:   Raqibul Islam
  3. TASK:   contest(5-6-10) - Dungeon Master
  4. ALGO:   3d-bfs
  5. STAT:  
  6. */
  7.  
  8.  
  9. #include <iostream>
  10. #include <sstream>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <cmath>
  14. #include <cctype>
  15. #include <cstring>
  16. #include <string>
  17. #include <algorithm>
  18. #include <vector>
  19. #include <map>
  20. #include <set>
  21. #include <list>
  22. #include <queue>
  23. #include <stack>
  24. using namespace std;
  25.  
  26. #define READ(x) freopen(x,"r",stdin);
  27. #define WRITE(x) freopen(x,"w",stdout);
  28. #define EPS 1e-10
  29.  
  30. #define SET(x) memset(x,-1,sizeof(x))
  31. #define CLR(x) memset(x,0,sizeof(x))
  32.  
  33. #define pii pair<int,int>
  34. #define vi vector<int>
  35. #define i64 __int64
  36.  
  37. #define _max(a,b) ((a)>(b)?(a):(b))
  38. #define _min(a,b) ((a)<(b)?(a):(b))
  39. #define _abs(x) ((x)<0?-(x):(x))
  40. #define sq(x) ((x)*(x))
  41. #define sz(x) x.size()
  42.  
  43. #define MAX 35
  44. #define INF 1<<24
  45.  
  46. int L, R, C;
  47.  
  48. struct node{
  49.     int level, row, col;
  50.     int color, dist;
  51.     char ch;
  52. } graph[MAX][MAX][MAX];
  53.  
  54. queue <node> Q;
  55.  
  56. void init_graph()
  57. {
  58.     int i, j, k;
  59.     for(i=0; i<MAX; i++)
  60.         for(j=0; j<MAX; j++)
  61.             for(k=0; k<MAX; k++)
  62.             {
  63.                 graph[i][j][k].level = i;
  64.                 graph[i][j][k].row = j;
  65.                 graph[i][j][k].col = k;
  66.                 graph[i][j][k].color = 0;
  67.                 graph[i][j][k].dist = INF;
  68.                 graph[i][j][k].ch = '#';
  69.             }
  70. }
  71.  
  72. void run_bfs()
  73. {
  74.     int tmp_level, tmp_row, tmp_col;
  75.     graph[Q.front().level][Q.front().row][Q.front().col].color = 2;
  76.    
  77.     tmp_level = Q.front().level;
  78.     tmp_row = Q.front().row - 1;
  79.     tmp_col = Q.front().col;
  80.     if(tmp_row>0 && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
  81.     {
  82.         graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
  83.         graph[tmp_level][tmp_row][tmp_col].color = 1;
  84.         Q.push(graph[tmp_level][tmp_row][tmp_col]);
  85.     }
  86.    
  87.     tmp_level = Q.front().level;
  88.     tmp_row = Q.front().row + 1;
  89.     tmp_col = Q.front().col;
  90.     if(tmp_row<=R && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
  91.     {
  92.         graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
  93.         graph[tmp_level][tmp_row][tmp_col].color = 1;
  94.         Q.push(graph[tmp_level][tmp_row][tmp_col]);
  95.     }
  96.    
  97.     tmp_level = Q.front().level;
  98.     tmp_row = Q.front().row;
  99.     tmp_col = Q.front().col - 1;
  100.     if(tmp_col>0 && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
  101.     {
  102.         graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
  103.         graph[tmp_level][tmp_row][tmp_col].color = 1;
  104.         Q.push(graph[tmp_level][tmp_row][tmp_col]);
  105.     }
  106.    
  107.     tmp_level = Q.front().level;
  108.     tmp_row = Q.front().row;
  109.     tmp_col = Q.front().col + 1;
  110.     if(tmp_col<=C && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
  111.     {
  112.         graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
  113.         graph[tmp_level][tmp_row][tmp_col].color = 1;
  114.         Q.push(graph[tmp_level][tmp_row][tmp_col]);
  115.     }
  116.    
  117.     tmp_level = Q.front().level - 1;
  118.     tmp_row = Q.front().row;
  119.     tmp_col = Q.front().col;
  120.     if(tmp_level>0 && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
  121.     {
  122.         graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
  123.         graph[tmp_level][tmp_row][tmp_col].color = 1;
  124.         Q.push(graph[tmp_level][tmp_row][tmp_col]);
  125.     }
  126.    
  127.     tmp_level = Q.front().level + 1;
  128.     tmp_row = Q.front().row;
  129.     tmp_col = Q.front().col;
  130.     if(tmp_level<=L && graph[tmp_level][tmp_row][tmp_col].color==0 && graph[tmp_level][tmp_row][tmp_col].ch!='#')
  131.     {
  132.         graph[tmp_level][tmp_row][tmp_col].dist = graph[Q.front().level][Q.front().row][Q.front().col].dist+1;
  133.         graph[tmp_level][tmp_row][tmp_col].color = 1;
  134.         Q.push(graph[tmp_level][tmp_row][tmp_col]);
  135.     }
  136.     Q.pop();
  137. }
  138.  
  139. int main()
  140. {
  141.     int i, j, k;
  142.     while(scanf("%d %d %d", &L, &R, &C)==3)
  143.     {
  144.         if(L==0 && R==0 && C==0)
  145.             break;
  146.         init_graph();
  147.        
  148.         for(i=1; i<=L; i++)
  149.             for(j=1; j<=R; j++)
  150.                 for(k=1; k<=C; k++)
  151.                     cin >> graph[i][j][k].ch;
  152.                    
  153.         /*for(i=1; i<=L; i++)
  154.             for(j=1; j<=R; j++)
  155.             {
  156.                 for(k=1; k<=C; k++)
  157.                 {
  158.                     printf("%c", graph[i][j][k].ch);
  159.                 }
  160.                 printf("\n");
  161.             }
  162.         */
  163.        
  164.         for(i=1; i<=L; i++)
  165.             for(j=1; j<=R; j++)
  166.                 for(k=1; k<=C; k++)
  167.                 {
  168.                     if(graph[i][j][k].ch == 'S')
  169.                     {
  170.                         graph[i][j][k].dist = 0;
  171.                         Q.push(graph[i][j][k]);
  172.                         break;
  173.                     }
  174.                 }
  175.        
  176.         while(!Q.empty())
  177.         {
  178.             if(graph[Q.front().level][Q.front().row][Q.front().col].color != 2)
  179.             run_bfs();
  180.         }
  181.         /*for(i=1; i<=L; i++)
  182.             for(j=1; j<=R; j++)
  183.             {
  184.                 for(k=1; k<=C; k++)
  185.                 {
  186.                     printf("%c", graph[i][j][k].ch);
  187.                 }
  188.                 printf("\n");
  189.             }
  190.         */
  191.        
  192.         int flag = 0;
  193.         int end_level, end_row, end_col;
  194.         for(i=1; i<=L; i++)
  195.             for(j=1; j<=R; j++)
  196.                 for(k=1; k<=C; k++)
  197.                 {
  198.                     if(graph[i][j][k].ch=='E' && graph[i][j][k].dist<INF)
  199.                     {
  200.                         end_level = i;
  201.                         end_row = j;
  202.                         end_col = k;
  203.                         flag = 1;
  204.                         break;
  205.                     }
  206.                 }
  207.         if(flag) printf ("Escaped in %d minute(s).\n", graph[end_level][end_row][end_col].dist);
  208.         else printf("Trapped!\n");
  209.     }
  210.     //system("pause");
  211.     return 0;
  212. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement