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