|
Дан клетчатый лист бумаги, в котором некоторые клетки закрашены.
Требуется найти кратчайший путь из левой верхней клетки в правую нижнюю.
Двигаться можно только по вертикали или горизонтали.
Input
Пустая клетка представлена символом '.', закрашенная - символом '#'.
Число строк и столбцов не превышает 500.
Output
Такое же представление лабиринта, в котором найденный путь изображен символом '*'
Sample
| Input | Output |
|---|
..........
.#..#.....
..#..####.
...#.#....
###.....##
.....##.#.
......#...
|
****......
.#.*#.....
..#**####.
...#*#....
###.****##
.....##*#.
......#***
|
Если пути не существует, выведите одно слово "IMPOSSIBLE"
| 
