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

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


 

Лабиринт с тигром

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

В средние века в замках Европы был популярен следующий вид казни: в лабиринт, в котором находился тигр, заводили раба. Рабу была известна карта лабиринта и его первоначальное расположение. Тигр обладал очень тонким обонянием, то есть он знал, где находится раб в любой момент времени и мог в кратчайшее время настигнуть раба и съесть, если мог.

Дана схема лабиринта в виде таблицы N×M. Вход в лабиринт находится в левой верхней клетке. В этом же месте находится раб в начальный момент времени. Выход из лабиринта находится в правой нижней клетке. Гарантируется, что от входа до выхода существует путь и что тигр находится в свободной клетке лабиринта. Также известно, что лабиринт ограничен сплошной стеной по периметру.

Необходимо определить длину кратчайшего пути раба до выхода, и сможет ли раб гарантированно выбраться из лабиринта живым, если за единицу времени как раб, так и тигр, могут переместиться в соседнюю по стороне клетку в произвольном свободном направлении (то есть туда, где нет стены).

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

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

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

В первой строке выходного файла OUTPUT.TXT выведите целое число – длину кратчайшего пути раба, во второй строке выведите «Yes», если раб гарантированно сможет добраться до выхода, и «No» в противном случае.

Примеры

INPUT.TXTOUTPUT.TXT
18 10
##########
#.#...##.#
#.#..###.#
#.#.##...#
#.......##
#...###..#
#....T#..#
##########
12
No
2 8 10
##########
#.#...##.#
#.#..###.#
#.#.##...#
#.......##
#..####..#
#....T#..#
##########
12
Yes

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


 Язык программирования 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 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru



вскрытие авто цена