e-olymp 432. Подземелье

Подземелье

   Вы попали в 3D подземный лабиринт и необходимо найти быстрый выход! Карта подземелья составлена из единичных кубических комнат, по которым можно или нельзя передвигаться. Нужно всего одну минуту, чтобы переместиться она одну единицу на север, юг, восток, запад, вверх или вниз. Вы не можете двигаться по диагонали, и лабиринт окружен твердой скальной породой со всех сторон.

   Можно ли выбраться из лабиринта? Если да, то какое времени это займет?

Техническое условие

   Входные данные

Состоит из ряда подземелий. Каждое описание подземелья начинается со строки, содержащей три целых числа: количество уровней в подземелье l, а также r и cколичество строк и столбцов, описывающих план каждого уровня (все числа не больше 30).

   Далее следует l блоков по r строк, каждая по c символов. Каждое число описывает одну ячейку подземелья. Запрещенные для перемещения кубы подземелья обозначены символом ‘#‘, а пустые клетки обозначены ‘.‘. Ваша стартовая позиция обозначается буквой ‘S‘, а выход буквой ‘Е‘. Все описания подземелий отделены пустой строкой. Описание входных данных заканчивается тремя нулями.

   Выходные данные

   Для каждого лабиринта необходимо вывести одну строку. Если есть возможность добраться до выхода, вывести строку вида

Escaped in X minute(s).

    где X — наименьшее время, необходимое для достижения выхода.

   Если достичь выход невозможно, вывести строку

   Trapped!


 

ТЕСТЫ:

Входные данные

Выходные данные

 

Тесты взяты с сайта e-olimp. Подтверждение прохождения задачи на e-olimp.

Задача (Подземелья)

 

Задача на E-Olimp!

ССЫЛКА НА IDEONE.COM

(Программа также проверенна в Code::Blocks)


Алгоритм решения:

Основа всего алгоритма — поиск в ширину, реализованный на трехмерном массиве.  Для реализации я использовал собственную структуру очереди. В двух словах идея такова:
1) Считываем данные, заполняя массив по принципу:  Если «комната закрыта» — ставим -1. Если открыта — ставим ноль. Старт и Финиш также заполняем нулями, но запоминаем их координаты.
Также создаем массив булевых переменных, помогающий нам определять, посещали ли мы уже эту вершину. Этот массив вначале заполняется нулями.
2) Реализация самого поиска. Создаем очередь и помещаем в нее стартовую вершину.  Затем запускаем цикл до тех пор, пока очередь не пуста.
3) Действия в цикле повторяются шесть раз, на каждое из возможных направлений.
  • Проверяем закрыта ли эта комната ( проверка на положительное число)
  • Если комната открыта, проверяем, есть ли в ней уже какое то время. Если да, то кладем в нее минимум из времени пути который был уже проложен, и проложен сейчас. В противном случае, кладем в нее время данного пути.
  • Проверяем, была ли посещена эта комната ранее. В противном случае — отмечаем что она посещалась и добавляем ее в очередь.

4) Извлекаем вершину из очереди.

В итоге мы получаем такой же трехмерный массив, в котором каждая клетка отмечена минимальным временем от старта. Так как расположение финиша мы запомнили, просто проверяем  его «вес». В зависимости от результата проверки выводим требуемый по условию результат.

Примечание! 

1)Для удобной реализации поиска, оба массива создаем на два уровня больше, как бы делая ему рамку ( маску).

2) Поскольку в одном тесте идет не один набор уровней, программа выполняется в цикле, который работает до тех пор, пока не получит в качестве трех чисел — три нуля. ( В комментариях назовем этот цикл «внешним»)


 

 

Царев Николай Александрович
Царев Николай Александрович

Latest posts by Царев Николай Александрович (see all)

One thought on “e-olymp 432. Подземелье

Добавить комментарий