Задача Soldier. В некотором (догадайтесь сами, в каком) воинственном государстве солдаты-призывники делают два дела: красят травку и ходят строем. И если с покраской все легко, то строевая подготовка требует много времени и сил, особенно при условии, когда вот-вот очередной военный парад... Плац, по которому будут шагать солдаты нашего героического взвода, представляет собой прямоугольник N×M(2≤N,M≤700) (если принять размер "коробки" взвода солдат за квадрат с единичной стороной), некоторые клеточки которого заняты другими подразделениями, поэтому взводу ходить через эти клеточки запрещается. Известны также начальный и конечный пункты движения взвода. Сержант Pupkin хорошо знает - солдаты отлично ходят по прямой, а вот команды "налево", "направо" и "кругом" выполняют иногда с ошибками, поэтому он хочет, чтобы на праздничном прохождении взвод сделал как можно меньше поворотов. Помогите сержанту найти маршрут с наименьшим количеством поворотов.
Технические условия. Программа Soldier читает из устройства стандартного ввода в первой строке N - количество строк в схеме плаца. Во второй строке M - количество столбиков. Дальше N строк по M символов в каждой. Символ "." означает свободную клеточку, символ "X" занятую. Также существует ровно один символ "S" и один символ "F", что помечают соответственно исходную и конечную точки прохода взвода. Хотя бы один маршрут между S и F всегда существует.
Программа выводит на устройство стандартного вывода единственное число - минимальное количество поворотов взвода на маршруте. Перед началом марша сержант может построить взвод лицами в любую сторону - как ему это удобно.
| Пример | |
|
Ввод 3 |
Вывод 1 |