Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Ладья в лабиринте

(Время: 1 сек. Память: 16 Мб Сложность: 54%)

Ладья – это шахматная фигура, которая за один ход может переместиться на любое количество клеток по горизонтали или вертикали. При этом она не может «перепрыгивать» через стоящие на ее пути фигуры.

Вася недавно соорудил на шахматной доске своеобразный лабиринт, поставив в некоторые клетки доски пешки (самые «слабые» шахматные фигуры). Теперь он хочет знать, за какое минимальное количество ходов ладья может добраться из одной клетки в другую, перемещаясь по свободным клеткам доски.

Он размышляет над этим вопросом уже несколько дней, однако найти ответ не может. Поэтому он решил обратиться за помощью к Вам. Напишите программу, находящую ответ на Васину задачу.

Входные данные

Первая строка входного файла INPUT.TXT содержит два натуральных числа: n и m (1 ≤ n, m ≤ 500) – размеры лабиринта.

Каждая из последующих n строк содержит m символов. j-ый символ i-ой из этих строк соответствует клетке с координатами (i, j). Он равен «.» (точка), если клетка пуста, «P», если занята пешкой, «S», если это начальная клетка для ладьи, и «F», если это конечная клетка.

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное количество ходов, требуемое ладье для того, чтобы из начальной клетки попасть в конечную. Если конечная клетка недостижима из начальной выведите -1.

Примеры

INPUT.TXTOUTPUT.TXT
14 4
F.PS
.PP.
.PP.
....
3
24 4
F.PS
.PP.
.PP.
.P..
-1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2007 / 2008 1 тур
 2007 / 2008 2 тур
 2007 / 2008 3 тур
 2008 / 2009 1 тур
 2008 / 2009 2 тур
 2008 / 2009 3 тур
 2009 / 2010 1 тур
 2009 / 2010 2 тур
 2009 / 2010 3 тур
 2010 / 2011 1 тур
 2010 / 2011 2 тур
 2010 / 2011 3 тур
 2011 / 2012 1 тур
 2011 / 2012 2 тур
 2011 / 2012 3 тур
 2012 / 2013 1 тур
 2012 / 2013 2 тур
 2012 / 2013 3 тур
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 2020 / 2021 7-8 классы
 2020 / 2021 9-11 классы
 2021 / 2022 7-8 классы
 2021 / 2022 9-11 классы
 2022 / 2023
 A. Сороконожка
 B. Сверхстепень
 C. Флаги
 D. Ладья в лабиринте

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru