Форум: "Потрепаться";
Текущий архив: 2003.10.16;
Скачать: [xml.tar.bz2];
ВнизРазминка для мозгов :) Найти похожие ветки
← →
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 вся ветка
Форум: "Потрепаться";
Текущий архив: 2003.10.16;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.117 c