eolymp
bolt
Try our new interface for solving problems
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.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122.17 MiB
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