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

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

HotLog


 

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

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

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

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

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

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

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

Пример

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

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Друзья
 B. Скачки
 C. Дерево
 D. Банкет
 E. Компоненты связности
 F. Удаление клеток
 G. Укладка плитки
 H. Раздел империи
 I. Покраска лабиринта
 J. Построение
 K. Рекурсия
 L. Производство деталей
 M. Доказательство теоремы
 N. Го
 O. Радио
 P. Конная прогулка

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru