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

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

HotLog


 

Конная прогулка

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

Требуется выполнить обход прямоугольного поля, перемещаясь в нем по правилам шахматного коня. В лабиринте имеются клетки, перемещение в которые невозможно. Начальная позиция коня определена. Необходимо посетить все клетки (в которые переход возможен) без повторных заходов. Гарантируется, что такой обход существует.

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

В первой строке входного файла INPUT.TXT содержится два натуральных числа N и M – размеры поля (N,M ≤ 100). Далее, следует карта поля: N строк по M символов в каждой строке. Символом «.» (точка) обозначается пустое пространство. Символ «X» указывает на то, что перемещение в данную клетку поля запрещено. Начальная позиция коня задается единственным в поле символом «K».

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

В выходной файл OUTPUT.TXT выведите матрицу обхода поля, в каждой ячейке которого должен быть вписан номер шага ее посещения (начиная с единицы). Клетки, помеченные как «X» во входных данных следует при выводе помечать нулевым значением. Числа следует разделять пробелами, допускается использовать лишние пробелы. В случае неоднозначного решения следует вывести любое.

Примеры

INPUT.TXTOUTPUT.TXT
15 5
K....
.....
.....
.....
.....
 1 14  9 20  3
24 19  2 15 10
13  8 25  4 21
18 23  6 11 16
 7 12 17 22  5
26 8
X......X
..K..X..
.....X..
..XXXX..
........
X......X
 0 11 32 23  2 21 30  0
33 24  1 10 31  0  3 20
12  9 38 25 22  0 16 29
37 34  0  0  0  0 19  4
 8 13 26 35  6 15 28 17
 0  6  7 14 27 18  5  0
39 9
....K....
.........
..XXXXX..
..X...X..
..X.X.X..
..X...X..
..XXXXX..
.........
.........
15 18 45 32  1 20 47 34  3
44 31 16 19 46 33  2 21 48
17 14  0  0  0  0  0  4 35
30 43  0 57 60 63  0 49 22
13 56  0 62  0 58  0 36  5
42 29  0 59 64 61  0 23 50
55 12  0  0  0  0  0  6 37
28 41 10 53 26 39  8 51 24
11 54 27 40  9 52 25 38  7

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

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

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