Путь коня

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

Технические условия

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

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

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

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

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 14.2857
Сложность: 8% 69/75
Классификация: Теория графов

Пример

Пример входных данных

Sample 1
5
.....
.@@..
.....
.....
.....

Sample 2
5
@..@.
..##.
.....
.....
.....

Sample 3
5
@....
..#..
.#...
.....
....@

Пример выходных данных

Sample 1
...@.
.@@..
....@
.....
.....

Sample 2
@..@.
..##.
.@..@
..@..
@....

Sample 3
Impossible

← Удаление клеток

Список задач