Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вся вода на поверхности Марса находится в замороженном состоянии.
Для упрощения доступа к воде все подземные поселения на Марсе имеют
выходы на замерзшее озеро.
Для передвижения по ледяному озеру
на поверхности были вморожены кубические блоки,
от которых нужно оттолкнуться для начала движения
(возможно отталкивание вбок).
От выхода из поселения можно начать движение в любом направлении.
Лед очень гладкий, поэтому остановиться можно, только уперевшись
в грань блока или край озера или достигнув выхода какого-либо поселения.
Напишите программу, которая рассчитает маршрут движения от одного поселения
до другого, используя минимальное количество отталкиваний.
Первая строка вода содержит два целых числа `N` и `M` (`3 <= N, M <= 200`) - размеры озера.
Далее следует `N` строк, содержащих по `M` символов. Символ ``'.'`` означает
гладкую поверхность озера, символ ``'#'`` - блок, ``'S'`` - выход стартового поселения,
``'E'`` - выход поселения, в которое нужно добраться. Гарантируется, что символы
``'S'`` и ``'E'`` встречаются ровно 1 раз.
Вывести одно целое число - минимальное количество отталкиваний при путешествии из одного поселения в другое.
Если достигнуть конечного выхода нельзя, то вывести -1.
```sample Пример ввода 1
6 8
........
...S..#.
..E.....
.#......
.....#..
........
```
```sample Пример вывода 1
4
```
Пояснение к примеру: сначала нужно скользить направо, затем до упора вниз, налево и вверх. Получается 4 отталкивания - от выхода стартового поселения и 3 блоков.
Если при первом отталкивании достичь берега озера, то далее можно будет
останавливаться только в углах озера.
Начало
Рабочее место участника
Поиск в ширину (BFS)