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

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

HotLog


 

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

(Время: 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++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Путь
 B. Один конь
 C. Табличка
 D. Грядки
 E. Звезда
 F. Морской бой - 3
 G. Два коня
 H. Лабиринт с тигром
 I. Алхимия
 J. Игра - 4
 K. Игра Jammed
 L. Числа
 M. Кладоискатель
 N. Водолей
 O. Lines - 2
 P. Ладья в лабиринте
 Q. Игрушечный лабиринт
 R. Лабиринт
 S. Мосты
 T. Цивилизация
 U. Только направо
 V. Герои
 W. Лабиринт минотавра
 X. Наименьшее кратное
 Y. Космические исследования
 Z. Кубик Рубика

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