Язык:

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

Задачи	Online статус	Соревнования
Новости	Справка	СДО

Регистрация || Вход/выход

Забыли пароль?

Рейтинг авторов

О системе

Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

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

Ограничение времени:	1 сек.
Ограничение памяти:	65536 КБайт
Баллы:	100

Статистика

Послать на проверку

Задачу добавил Неизвестный

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

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

Первая строка входных данных содержит два целых числа N и M — размеры лабиринта. Каждая из следующих N строк содержит M символов '.' или '#', где символ '.' означает пустую клетку, а '#' — закрашенную.

Число строк и столбцов не превышает 500.

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

Выведите такое же изображение лабиринта, что и во входных данных (размеры выводить не надо), в котором найденный путь изобразите символом '*'.

Если пути не существует, выведите одно слово "IMPOSSIBLE". Если сущестует несколько кратчайших путей, выведите любой.

Пример

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