Путь коня

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

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

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

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

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

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]