Məsələlər
Atın yolu
Atın yolu
\textbf{n}×\textbf{n} xanalı şahmat lövhəsi verilir, xanalardan bəziləri kəsilmişdir. Kəsilməmiş xanalardan at gedişi ilə keçməklə ən qısa yolla bir xanadan digər xanaya keçin.
\InputFile
Birinci sətirdə \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{50}) ədədi verilir. Növbəti \textbf{n} sətrin hər birində \textbf{n işarə verilir. }# işarəsi ilə kəsilmiş xana, nöqtə işarəsi ilə - kəsilməmiş xana, @ - işarəsi ilə (belə işarədən iki dənədir) atın yolunun başlanğıc və son xanası qeyd olunur.
\OutputFile
Əgər yol qurmaq mümkün deyilsə, "\textbf{Impossible}" verməli. Əks halda girişdəki kimi eyni kartı verin, lakin atın bütün aralıq gedişlərini @ işarəsi ilə işarələyin.
Giriş verilənləri #1
5 ..... .@@.. ..... ..... .....
Çıxış verilənləri #1
..... .@@.. ...@. .@... .....
Giriş verilənləri #2
5 @..@. ..##. ..... ..... .....
Çıxış verilənləri #2
@..@. ..##. .@@.. ...@. .@...
Giriş verilənləri #3
5 @.... ..#.. .#... ..... ....@
Çıxış verilənləri #3
Impossible