Скачать: CL | DM;

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

← →
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]

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

---

← →
Igorek ©   (2003-09-27 13:46) [2]

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

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.45 MB
Время: 0.025 c