Мосты

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

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

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

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

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

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

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

Примеры

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

[Обсуждение] [Все попытки] [Лучшие попытки]