|
Поход за грибами
(Время: 5 сек. Память: 128 Мб Сложность: 67%)
Однажды грибник Макар попал в трёхмерный лес, в котором растут деревья и грибы. Лес состоит из H уровней, расположенных друг над другом. Каждый уровень – это прямоугольная площадка, разбитая на N×M участков. Макар может свободно перемещаться по свободным участкам в шести направлениях: вверх, вниз, влево, вправо, вперед и назад. Оказавшись на одном участке с грибом, Макар может его сорвать. Однако сквозь деревья и за пределы леса Макар ходить не может. При любом перемещении из одного участка в смежный Макар делает один шаг.
У Макара есть карта леса, включающая расположение деревьев и грибов в нём, а также текущее положение Макара. Некоторые грибы (возможно, все) могут быть недостижимы.
Требуется определить: какое максимальное число грибов сможет собрать Макар и какое минимальное количество шагов ему на это потребуется.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа H, N, M – размеры леса
(2 ≤ H, N, M ≤ 50). Далее идет описание H уровней снизу вверх. Каждый уровень описывается N строками по M символов в каждой: «.» обозначает свободный участок, «#» – дерево, заглавная буква английского алфавита «M» – гриб и заглавная буква английского алфавита «P» – положение Макара. Описание каждого уровня завершается пустой строкой. Гарантируется, что количество грибов на карте не превосходит 20.
Выходные данные
В выходной файл OUTPUT.TXT выведите два целых числа: максимальное число грибов, которые может собрать Макар, и минимальное количество шагов, которые Макар должен сделать, чтобы собрать эти грибы.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3 3 3
...
##.
.M.
###
P.#
.##
M##
#..
#.M
| 2 10 |
Система оценки
Решения, работающие только для H, N, M ≤ 10, будут оцениваться в 40 баллов.
Решения, работающие только для решений с не более чем 10 грибами, будут оцениваться в 80 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |