Разминка для мозгов :)

← →
Pat © (2003-09-26 22:55) [0]

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

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

Входной файл INPUT.TXT состоит из описаний нескольких пещер. Описание каждой пещеры начинается со строки с тремя целыми числами L, R и C ( все числа не больше 30). L – количество уровней в пещере, R, C – количество строк и колонок в плане каждого этажа. Далее следуют L блоков данных, каждый из которых представляет R строк, содержащих C символов. Каждый символ описывает ячейку пещеры. Стены обозначены символом ‘#’, а ячейки где проход разрешен ‘.’ (точкой) . Начальная позиция указывается символом ‘S’, а выход символом ‘E’. После описания каждого уровня пещеры следует ровно одна пустая строка. Ввод завершается строкой, содержащей три нуля в качестве L, R, C.

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

Каждой пещере в выходном файле OUTPUT.TXT должна соответствовать одна строка. Если Вы нашли выход, то вид строки следующий:

Вышли за x минут.

где x кратчайшее время, за которое возможен выход. Если вам не удалось найти выход, напечатайте строчку:

Ловушка!

Пример входных данных 3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0 Пример выходных данных Выщли за 11 минут. Ловушка!

← →
Asteroid © (2003-09-26 23:54) [1]

Волновой алгоритм...ничего нового :)

> Asteroid © (26.09.03 23:54) [1]
> Волновой алгоритм...ничего нового :)

Вараинтов того же самого волнового алгоритма есть несколько. Вообще поиск пути на карте - интересная задача. А тут трехмерный вариант. Как вы построите фронт волны? Расширяющийся шар или пузырь? Его части могут расходится, потом сходится. Надо непростую геометрию программировать. И переводить на дискретное пространство.

Разминка для мозгов :) Найти похожие ветки