Змей Горыныч оказался в лабиринте и хочет выбраться из него как можно скорее. К сожалению, после вчерашнего употребления кефира, левая голова Змея соображает плохо.
Поэтому Змей Горыныч может поворачивать направо и идти прямо, но не может поворачивать налево и разворачиваться на месте.
Помогите Змею Горынычу определить длину кратчайшего пути до выхода из лабиринта.
Входные данные
В первой строке через пробел записаны числа r и c (4 ≤ r, c ≤ 20) - количество строк и столбцов в карте лабиринта.
В каждой из следующих r строк записано по c символов, задающих эту карту.
Символ S обозначает положение Змея Горыныча, символ F - точку выхода из лабиринта, символ X - стенку. Пробелами обозначены проходимые клетки.
Гарантируется, что лабиринт окружен стенами. Перед началом движения Змей Горыныч может сориентироваться по любому из 4 направлений (вверх, вниз, влево или направо).
Выходные данные
Выведите единственное число - расстояние, которое придется пройти Змею Горынычу.
Гарантируется, что он всегда сможет выйти из лабиринта.
Пояснение к примеру
Змей Горыныч начинает двигаться направо и его маршрут обозначен точками.
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
Примеры
| входные данные |
выходные данные |
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
|