Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход |
Некий воитель с копьём на лошади, известный как Лансьер, должен пройти путь от стартовой позиции до конечной на шахматной доске. Лансьер может двигаться двумя способами:
Изображение ниже показывает, каким образом передвигается шахматный конь:
Шахматная доска представляет собой матрицу n ⋅ n, где "." обозначает свободную клетку, а "#" - занятую какой-либо фигурой. Стартовая позиция Лансьера обозначена символом "L", конечная - символом "F".
Определите, сможет ли Лансьер добраться до требуемой позиции, и если да, то выведите минимальное количество ходов, которые ему необходимо совершить, а если нет, выведите -1.
В первой строке вводится единственное число n (2 ≤ n ≤ 1000) - размерность шахматной доски
В следующих n строках вводится n символов "." или "#", обозначающие свободные или занятые клетки, а также символы "L" и "F" обозначающие начальную и конечную позицию Лансьера. Задачей гарантируется, что обязательно существует ровно одна начальная и одна конечная позиция.
Выведите одно число - минимальное возможное количество ходов Лансьера из начальной позиции в конечную, а если невозможно достигнуть конечной позиции - выведите -1
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|