Задача G. Лансьер

Автор:Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

Изображение ниже показывает, каким образом передвигается шахматный конь:

Шахматная доска представляет собой матрицу n ⋅ n, где "." обозначает свободную клетку, а "#" - занятую какой-либо фигурой. Стартовая позиция Лансьера обозначена символом "L", конечная - символом "F".

Определите, сможет ли Лансьер добраться до требуемой позиции, и если да, то выведите минимальное количество ходов, которые ему необходимо совершить, а если нет, выведите -1.

Формат входных данных

В первой строке вводится единственное число n (2 ≤ n ≤ 1000) - размерность шахматной доски

В следующих n строках вводится n символов "." или "#", обозначающие свободные или занятые клетки, а также символы "L" и "F" обозначающие начальную и конечную позицию Лансьера. Задачей гарантируется, что обязательно существует ровно одна начальная и одна конечная позиция.

Формат выходных данных

Выведите одно число - минимальное возможное количество ходов Лансьера из начальной позиции в конечную, а если невозможно достигнуть конечной позиции - выведите -1

Примеры тестов

Стандартный вход Стандартный выход
1
8
.......F
......#.
####....
######.#
.....#.#
#.#.#..#
..######
.......L
3

0.080s 0.015s 15