Задача 31: Лошадью ходи! (DOOI)
Даны обозначения двух полей шахматной
доски, на которых стоят конь и пешка. Найти минимальное количество
ходов, за которые конь доберется до пешки, если последняя стоит на
месте. Координаты коня и пешки задаются как натуральные числа, от
левого нижнего угла шахматной доски.
Формат входных данных:
Первая строка входного файла input.txt содержит пару натуральных
чисел, координаты коня; вторая - пару чисел, координаты пешки.
Формат выходных данных:
Выходной файл output.txt содержит одно число - количество ходов
коня (можно и последовательные координаты этих ходов).
input.txt:
3 4
6 4
output.txt:
3
Решение:
Задача, присланная нашими партнерами по ДООИ. Ее надо решить двум
командам, но я решил, что партнеры не обидятся, если я разберу их
задачу на своем сайте.
Первая идея, которая пришла мне в голову - рекурсивное решение. Идея
неправильная (было установлено опытным путем - полный перебор жутко
тормозная вещь). Вторая идея это нерекурсивный флуд (заливка) всего
поля. Заполним всю доску кодом 255 (чтоб не путаться). От начальной
позиции (присвоим этой клетке на доске значение 0) во все возможные
позиции, на которые конь может переместиться за один ход, ставим 1.
Затем сканируем всю доску, как только нашли значение 1 во все
возможные клетки, куда конь может сходить ставим 2, но это только в
том случае, если там стоит 255, т.е. конь там еще не был, иначе
получится не кратчайший маршрут. Повторяем сканирование для 2, 3 и
т.д. до тех пор, пока в одной из свежезаполненных клеток не
напоремся на пешку. Если это произошло, то выводим значение из этой
клетки - кратчайшее расстояние до позиции коня.
Теперь перейдем ко второму вопросу (можно, значит нужно). Заведем
массив для хранения координат коня размерностью 64 (а вдруг долго
топтаться будет). Вот теперь-то нам и пригодится рекурсия (хорошо,
что я свою процедуру закомментировал, а не стер!). От конечной
позиции (где стоит пешка) проверяем все возможные клетки, откуда
туда мог прийти конь (на 1 меньше чем кол-во ходов итоговое). Как
только найдем, занесем в элемент массива с номером, равным итоговому
количеству ходов коня его координаты, затем уменьшаем счетчик,
изначально равный количеству ходов коня до пешки, на 1. Запускаем
рекурсивную процедуру для позиции, откуда пришел конь и т.д. В конце
(когда дойдем до клеточки со значением 1 - первый ход) выводим все
содержимое массива. Для примера из условия это: 5,5 7,6 6,4.
Я конечно понимаю, что рекурсия - вещь неудобоваримая, но лично я ее
освоил еще в 8-ом классе, и даже написал научную работу на эту тему.
Если что-то непонятно - пишите на мыло, буду пытаться объяснить :)
Далее
ð
