fork(1) download
copy 
  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
comments (?)
stdin
copy 
3 4 5
S....
.###.
.##..
###.#

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

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

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

0 0 0
stdout
copy 
Escaped in 11 minute(s).
Trapped!
https://ideone.com/t9twO2
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!