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

Условие

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

• Как обычный конь, с шагами в форме буквы "Г" и возможностью перепрыгивать другие фигуры.
• Как ладья, с шагами по вертикали или горизонтали на любое количество клеток, но без возможности перепрыгивать другие фигуры.

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

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

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

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

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

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

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

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

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

8
.......F
......#.
####....
######.#
.....#.#
#.#.#..#
..######
.......L

3