|
Лабиринт минотавра
(Время: 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.TXT | OUTPUT.TXT |
1 | 2 2
T#
#K | 1 |
2 | 5 5
-----
-T-K-
-.-.-
-...-
----- | No way 6 2 |
3 | 5 5
.#.#.
#T#.#
#...#
.#.#.
..#.K | No way No key |
4 | 10 5
#####
#T..#
###.#
#...#
#.###
#...#
###.#
#...#
#K###
##### | No way 15 No way |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |