Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Поход за грибами

(Время: 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.TXTOUTPUT.TXT
13 3 3
...
##.
.M.

###
P.#
.##

M##
#..
#.M

2 10

Система оценки

Решения, работающие только для H, N, M ≤ 10, будут оцениваться в 40 баллов.

Решения, работающие только для решений с не более чем 10 грибами, будут оцениваться в 80 баллов.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 Седьмая командная олимпиада
 A. Винни-Пух
 B. Игра в 8
 C. Треугольник в прямоугольнике
 D. Поход за грибами
 E. Башенки из кубиков
 F. Весёлые качели
 G. Площадь многоугольника
 H. Мирные ладьи

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru