fork(1) download
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct node{
  6. int x,y,z;
  7. node *prev;
  8. node (int x0, int y0, int z0, node* las) { x = x0; y=y0; z=z0; prev = las;}
  9. node();
  10. }; //Структура "Узел" используемая в структуре "Очередь"
  11.  
  12. struct quene{ //Структура "Очередь"
  13. int k=0;
  14. node *last=NULL;
  15. node *first=NULL;
  16. node *tmp=NULL;
  17.  
  18. void push( int n, int m, int g){
  19. node* x = new node(n,m,g, NULL);
  20. k++;
  21. if(k!=1)
  22. last->prev = x;
  23. last = x;
  24. if(k==1)
  25. first=x;
  26. }
  27.  
  28. void pop(){
  29. tmp=first;
  30. first=first->prev;
  31. delete tmp;
  32. k--;
  33. }
  34.  
  35. };
  36.  
  37.  
  38.  
  39. int main()
  40. {
  41. int l,r,c;
  42. cin >> l >> r >> c;
  43. while((l!=0)&&(r!=0)&&(c!=0)){ //Внешний цикл
  44. int mas[l+2][r+2][c+2];
  45. bool masb[l+2][r+2][c+2];
  46. char u;
  47. int st1,st2,st3;
  48. int fs1,fs2,fs3;
  49. for(int i1=0; i1<l+2; i1++){ //Начало считывания и обработки данных
  50. for(int i2=0; i2<r+2; i2++){
  51. for(int i3=0; i3<c+2; i3++){
  52. masb[i1][i2][i3]=0;
  53. if((i1==0)||(i2==0)||(i3==0)||(i1==l+1)||(i2==r+1)||(i3==c+1))
  54. mas[i1][i2][i3]=-1;
  55. else{
  56. cin>>u;
  57. if(u=='#'){
  58. mas[i1][i2][i3]=-1;}
  59. if(u=='.'){
  60. mas[i1][i2][i3]=0;
  61. }
  62. if(u=='S'){
  63. mas[i1][i2][i3]=0;
  64. st1=i1;st2=i2;st3=i3;
  65. }
  66. if(u=='E'){
  67. mas[i1][i2][i3]=0;
  68. fs1=i1;fs2=i2;fs3=i3;
  69. }
  70. }
  71. }
  72. }
  73. } // Конец обработки
  74.  
  75. quene ts; //Создание очереди
  76. ts.push(st1,st2,st3);// Кладем в нее "стартовую" вершину
  77. while(ts.k!=0){ //Запускаем поиск
  78. int x1=ts.first->x;
  79. int y1=ts.first->y;
  80. int z1=ts.first->z; //Для удобства сохраняем координаты
  81. //обрабатываемой вершины в специальных переменных
  82.  
  83. if(mas[x1+1][y1][z1]>=0){ // Вершина справа
  84. if(mas[x1+1][y1][z1]!=0)
  85. mas[x1+1][y1][z1]=min(mas[x1+1][y1][z1],mas[x1][y1][z1]+1);
  86. else
  87. mas[x1+1][y1][z1]=mas[x1][y1][z1]+1;
  88. if(masb[x1+1][y1][z1]==0){
  89. masb[x1+1][y1][z1]=1;
  90. ts.push(x1+1,y1,z1);
  91. }
  92. }
  93.  
  94. if(mas[x1-1][y1][z1]>=0){ //Вершина слева
  95. if(mas[x1-1][y1][z1]!=0)
  96. mas[x1-1][y1][z1]=min(mas[x1-1][y1][z1],mas[x1][y1][z1]+1);
  97. else
  98. mas[x1-1][y1][z1]=mas[x1][y1][z1]+1;
  99. if(masb[x1-1][y1][z1]==0){
  100. masb[x1-1][y1][z1]=1;
  101. ts.push(x1-1,y1,z1);
  102. }
  103. }
  104.  
  105. if(mas[x1][y1+1][z1]>=0){ //Вершина вверху
  106. if(mas[x1][y1+1][z1]!=0)
  107. mas[x1][y1+1][z1]=min(mas[x1][y1+1][z1],mas[x1][y1][z1]+1);
  108. else
  109. mas[x1][y1+1][z1]=mas[x1][y1][z1]+1;
  110. if(masb[x1][y1+1][z1]==0){
  111. masb[x1][y1+1][z1]=1;
  112. ts.push(x1,y1+1,z1);
  113. }
  114. }
  115.  
  116. if(mas[x1][y1-1][z1]>=0){ //Вершина внизу
  117. if(mas[x1][y1-1][z1]!=0)
  118. mas[x1][y1-1][z1]=min(mas[x1][y1-1][z1],mas[x1][y1][z1]+1);
  119. else
  120. mas[x1][y1-1][z1]=mas[x1][y1][z1]+1;
  121. if(masb[x1][y1-1][z1]==0){
  122. masb[x1][y1-1][z1]=1;
  123. ts.push(x1,y1-1,z1);
  124. }
  125. }
  126.  
  127. if(mas[x1][y1][z1+1]>=0){ //Вершина на уровень выше
  128. if(mas[x1][y1][z1+1]!=0)
  129. mas[x1][y1][z1+1]=min(mas[x1][y1][z1+1],mas[x1][y1][z1]+1);
  130. else
  131. mas[x1][y1][z1+1]=mas[x1][y1][z1]+1;
  132. if(masb[x1][y1][z1+1]==0){
  133. masb[x1][y1][z1+1]=1;
  134. ts.push(x1,y1,z1+1);
  135. }
  136. }
  137.  
  138. if(mas[x1][y1][z1-1]>=0){ //Вершина на уровень ниже
  139. if(mas[x1][y1][z1-1]!=0)
  140. mas[x1][y1][z1-1]=min(mas[x1][y1][z1-1],mas[x1][y1][z1]+1);
  141. else
  142. mas[x1][y1][z1-1]=mas[x1][y1][z1]+1;
  143. if(masb[x1][y1][z1-1]==0){
  144. masb[x1][y1][z1-1]=1;
  145. ts.push(x1,y1,z1-1);
  146. }
  147. }
  148. ts.pop(); //Удаление обработанной вершины из очереди
  149.  
  150. }
  151. if(mas[fs1][fs2][fs3]!=0) // Последняя проверка результата
  152. cout <<"Escaped in " << mas[fs1][fs2][fs3] << " minute(s)."<< endl;
  153. else
  154. cout << "Trapped!" << endl;
  155. cin >> l >> r >> c; // Считываение чисел для внешнего цикла
  156. }
  157. return 0;
  158.  
  159. }
Success #stdin #stdout 0s 3236KB
stdin
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0
stdout
Escaped in 11 minute(s).
Trapped!