eolymp
Соревнования

11.02 Старшая лига

Путь коня

Дана шахматная доска, состоящая из n × n клеток, несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной клетки в другую.

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

В первой строке задано число n (2n50). В следующих n строках содержится по n символов. Символом # обозначена вырезанная клетка, точкой - невырезанная клетка, @ - начальная и конечная клетки пути коня (таких символов два).

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

Если путь построить невозможно, то вывести "Impossible". В противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом @.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
5
.....
.@@..
.....
.....
.....
Выходные данные #1
.....
.@@..
...@.
.@...
.....
Входные данные #2
5
@..@.
..##.
.....
.....
.....
Выходные данные #2
@..@.
..##.
.@@..
...@.
.@...
Входные данные #3
5
@....
..#..
.#...
.....
....@
Выходные данные #3
Impossible