АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

246. Путь в лабиринте

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Неизвестный

Дан клетчатый лист бумаги, в котором некоторые клетки закрашены. Требуется найти кратчайший путь из левой верхней клетки в правую нижнюю. Двигаться можно только по вертикали или горизонтали.

Исходные данные

Пустая клетка представлена символом '.', закрашенная - символом '#'. Число строк и столбцов не превышает 500.

Результат

Такое же представление лабиринта, в котором найденный путь изображен символом '*'

Пример

Исходные данныеРезультат
..........
.#..#.....
..#..####.
...#.#....
###.....##
.....##.#.
......#...
****......
.#.*#.....
..#**####.
...#*#....
###.****##
.....##*#.
......#***

Если пути не существует, выведите одно слово "IMPOSSIBLE"


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Графы /
195. Поможем МПС 246. 9. Сеть 297. Скачки 64. Считай путем
Учебные курсы / Алгоритмы и структуры данных / Алгоритмы на графах /
207. Открытки и конверты 246. 9. Сеть 297. Скачки 247. Удаление клеток
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2020 / Импульс-2020, графы /
1968. 04 - Эвакуация 246. 208. 06 - Михаил Густокашин против бюрократии 205. 07 - Игра в города 805. 08 - Двудольность графа
 
время генерации 0.25 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.