Тура у лабіринті#1746
Тура — це шахова фігура, яка за один хід може переміститися на будь-яку кількість клітин по горизонталі або вертикалі. При цьому вона не може «перестрибувати» через фігури, які стоять на її шляху.
Вася нещодавно створив на шаховій дошці своєрідний лабіринт — у деякі клітини дошки він поставив пішаків (найбільш слабкі шахові фігури). Тепер він хоче дізнатися, за яку мінімальну кількість ходів тура може дістатися з однієї клітини в іншу.
Він думає над цим питанням вже кілька днів, однак відповіді знайти не може. Тому звернувся по допомогу до вас. Напишіть програму, що знайде відповідь на Васину задачу.
У першому рядку вхідного файлу містяться два натуральних числа: та (1 \le n, m \le 500) — розміри лабіринту.
Кожен з наступних рядків містить символів. -ий символ -ого з цих рядків відповідає клітинці з координатами . Він дорівнює "." (крапка), якщо клітинка порожня, P, якщо зайнята пішаком, S, якщо це початкова клітинка для тури, F, якщо це кінцева клітинка.
У вихідний файл виведіть мінімальну кількість ходів, необхідних турі, щоб із початкової клітинки дістатися до кінцевої. Якщо кінцева клітинка недосяжна з початкової, виведіть -1.
Приклад 1