Задачі
Шлях коня
Шлях коня
Задано шахову дошку, яка складається з \textbf{n}×\textbf{n} клітинок, декілька з яких вирізано. Провести ходом коня через невирізані клітинки шлях мінімальної довжини з однієї клітинки в іншу.
\InputFile
У першому рядку задано число \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{50}). У наступних \textbf{n} рядках міститься по \textbf{n} символів. Символом # позначено вирізану клітинку, точкою - невирізану клітинку, @ - задані клітинки (таких символів два).
\OutputFile
Якщо шлях побудувати неможливо вивести "\textbf{Impossible}", у противному випадку вивести таку ж карту, як і на вході, але помітити всі проміжні положення коня символом @.
Вхідні дані #1
5 ..... .@@.. ..... ..... .....
Вихідні дані #1
..... .@@.. ...@. .@... .....
Вхідні дані #2
5 @..@. ..##. ..... ..... .....
Вихідні дані #2
@..@. ..##. .@@.. ...@. .@...
Вхідні дані #3
5 @.... ..#.. .#... ..... ....@
Вихідні дані #3
Impossible