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

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


 

Лабиринт минотавра

(Время: 2 сек. Память: 32 Мб Сложность: 55%)

Вы слышали про игру «Лабиринт минотавра»? В этой игре бесстрашный герой Тесей пытается выбраться из запутанного лабиринта. Лабиринт имеет прямоугольную форму – N×M клеток. За один ход Тесей может перейти на соседнюю свободную клетку по вертикали или по горизонтали, либо, если он находится на краю лабиринта, покинуть его. Клетка может быть либо свободной, либо занятой стеной или дверью. Сквозь стены проход невозможен. Сквозь двери можно проходить только при наличии ключа, который подходит ко всем дверям и хранится где-то в лабиринте!

Для поиска выхода из лабиринта Тесей применяет специальную тактику:

  • Сначала он пытается найти выход по свободным клеткам.
  • Если Тесею это не удается – он пытается отыскать ключ, чтобы открывать им двери и искать путь на свободу.

По карте лабиринта требуется определить, сможет ли Тесей выбраться из лабиринта, или же ему придется остаться в этом ужасном месте.

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – длина и ширина лабиринта (2 ≤ N, M ≤ 1000). Далее идет N строк по M символов – описание лабиринта. Свободные клетки обозначены символом «.», стены – символом «#», двери – символом «-», «T» – положение Тесея в начальный момент времени, «K» – свободная клетка с ключом. Гарантируется, что в лабиринте только один Тесей и только один ключ.

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

В выходной файл OUTPUT.TXT выведите:

  • Если Тесей может выйти за пределы лабиринта без ключа – минимальное количество ходов, которое для этого понадобится.
  • Если не может – напечатать «No way» (без кавычек) и дополнительно через пробел вывести:
    • минимальное количество ходов, которое понадобится, чтобы добраться из начальной позиции Тесея до ключа;
    • «No key» (без кавычек) - если ключ недостижим.
    • Если ключ достижим, то следует дополнительно через пробел вывести:
      • минимальное количество ходов после взятия ключа, которое понадобится для того, чтобы покинуть лабиринт;
      • «No way» (без кавычек) – если даже с ключом нельзя выбраться из лабиринта.

Примеры

INPUT.TXTOUTPUT.TXT
12 2
T#
#K
1
25 5
-----
-T-K-
-.-.-
-...-
-----
No way 6 2
35 5
.#.#.
#T#.#
#...#
.#.#.
..#.K
No way No key
410 5
#####
#T..#
###.#
#...#
#.###
#...#
###.#
#...#
#K###
#####
No way 15 No way

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


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 A. Станки
 B. Распродажа
 C. Последовательность
 D. Обратное число
 E. Шифровка
 F. Формула
 G. Экзамены
 H. Отрезок
 I. Лабиринт минотавра
 J. Квадрат

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