Лабиринт с тигром
(Время: 2 сек. Память: 32 Мб Сложность: 48%)
В средние века в замках Европы был популярен следующий вид казни: в лабиринт, в котором находился тигр, заводили раба. Рабу была известна карта лабиринта и его первоначальное расположение. Тигр обладал очень тонким обонянием, то есть он знал, где находится раб в любой момент времени и мог в кратчайшее время настигнуть раба и съесть, если мог.
Дана схема лабиринта в виде таблицы N×M. Вход в лабиринт находится в левой верхней клетке. В этом же месте находится раб в начальный момент времени. Выход из лабиринта находится в правой нижней клетке. Гарантируется, что от входа до выхода существует путь и что тигр находится в свободной клетке лабиринта. Также известно, что лабиринт ограничен сплошной стеной по периметру.
Необходимо определить длину кратчайшего пути раба до выхода, и сможет ли раб гарантированно выбраться из лабиринта живым, если за единицу времени как раб, так и тигр, могут переместиться в соседнюю по стороне клетку в произвольном свободном направлении (то есть туда, где нет стены).
Входные данные
Первая строка входного файла INPUT.TXT содержит два числа: N и M – длина и ширина лабиринта (4 ≤ N, M ≤ 1000). Далее следует N строк по M символов – описание лабиринта. Символ «#» означает стену, а символ «.» - свободное пространство, «T» - положение тигра в начальный момент времени.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите целое число – длину кратчайшего пути раба, во второй строке выведите «Yes», если раб гарантированно сможет добраться до выхода, и «No» в противном случае.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 8 10
##########
#.#...##.#
#.#..###.#
#.#.##...#
#.......##
#...###..#
#....T#..#
########## | 12
No |
| 2 |
8 10
##########
#.#...##.#
#.#..###.#
#.#.##...#
#.......##
#..####..#
#....T#..#
########## | 12
Yes |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
