Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Путь коня

(Время: 1 сек. Память: 16 Мб Сложность: 46%)

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
15
.....
.@@..
.....
.....
.....
...@.
.@@..
....@
.....
.....
25
@..@.
..##.
.....
.....
.....
@..@.
..##.
.@..@
..@..
@....
35
@....
..#..
.#...
.....
....@
Impossible

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483