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

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

HotLog


 

Мосты

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

Вася живет в городе С.-П. Не нужно говорить (это итак все знают), что в городе С.-П. очень много мостов. И, как любому человеку, Васе часто нужно добираться из пункта A в пункт Б.

У Васи есть детальная карта города С.-П. Карта представляет собой квадратную решетку, размером N×M, где каждая ячейка – либо свободное пространство, по которому можно двигаться, либо препятствие (дома, водоемы, и т. п.), либо мост. Север, как обычно, находится вверху карты. Все мосты расположены с запада на восток (или с востока на запад). Это значит, что если Вася войдет в клетку с мостом с запада или востока, то он окажется на мосту, и выйти с этой клетки он может только на запад или на восток. Если же Вася войдет в клетку с мостом с юга или севера, то он окажется под мостом, и выйти сможет только на юг или на север.

Помогите Васе – посчитайте, сколько клеток карты ему нужно пройти, чтобы попасть из пункта А в пункт Б (умножить ваш ответ на масштаб карты Вася может и сам).

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – размеры карты (N, M ≤ 100). Следующие N строк содержат саму карту (по M символов в каждой строке). Символ «.» соответствует пустому пространству, символ «#» – препятствию, «B» – мосту, «S» – стартовой точке маршрута, «E» – конечной точке маршрута. Стартовая и конечная точки находятся на пустом пространстве.

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

В выходной файл OUTPUT.TXT выведите длину кратчайшего маршрута между начальной и конечной точкой или -1, если такого маршрута не существует.

Примеры

INPUT.TXTOUTPUT.TXT
11 2
SE
1
22 3
SB.
#E#
-1
33 3
#E#
SB.
#..
6

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Путь
 B. Один конь
 C. Табличка
 D. Грядки
 E. Звезда
 F. Морской бой - 3
 G. Два коня
 H. Лабиринт с тигром
 I. Алхимия
 J. Игра - 4
 K. Игра Jammed
 L. Числа
 M. Кладоискатель
 N. Водолей
 O. Lines - 2
 P. Ладья в лабиринте
 Q. Игрушечный лабиринт
 R. Лабиринт
 S. Мосты
 T. Цивилизация
 U. Только направо
 V. Герои
 W. Лабиринт минотавра
 X. Наименьшее кратное
 Y. Космические исследования
 Z. Кубик Рубика

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