|
Только направо
(Время: 1 сек. Память: 16 Мб Сложность: 60%)
Змей Горыныч оказался в лабиринте и хочет выбраться из него как можно скорее. К сожалению, после вчерашнего употребления кефира, левая голова Змея соображает плохо. Поэтому Змей Горыныч может поворачивать направо и идти прямо, но не может поворачивать налево и разворачиваться на месте. Помогите Змею Горынычу определить длину кратчайшего пути до выхода из лабиринта.
Входные данные
В первой строке входного файла INPUT.TXT через пробел записаны числа N и M (4 ≤ N, M ≤ 20) – количество строк и столбцов в карте лабиринта. В каждой из следующих N строк записано по M символов, задающих эту карту. Символ «S» обозначает положение Змея Горыныча, символ «F» – точку выхода из лабиринта, символ «X» – стенку. Пробелами обозначены пустые клетки. Гарантируется, что лабиринт окружен стенами, и Змей Горыныч всегда сможет выйти из лабиринта. Перед началом движения Змей Горыныч может сориентироваться по любому из 4 направлений (вверх, вниз, влево или направо).
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число – расстояние, которое придется пройти Змею Горынычу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 10 14
XXXXXXXXXXXXXX
X XXX
X XFXXXXX X
XXX XX XX X
X S X
XX XXXXXX X X
X X X X
X X X X X
XXX XX X
XXXXXXXXXXXXXX | 29 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
