UniLecs #Task. Кратчайший путь двух коней
Задача: на шахматной доске 8×8 стоит два шахматных коня и для каждого из них задана клетка, в которую он должен попасть. Переведите каждого из двух коней в заданную конечную клетку за наименьшее суммарное число ходов.
Примечание: два коня не могут одновременно находиться в одной клетке, но могут ходить в любом порядке (не обязательно по очереди).
Входные данные:
- (x1, x2) — x1 — начальная позиция 1го коня, x2 — позиция, куда необходимо переместить 1го коня,
- (y1, y2) — y1 — начальная позиция 2го коня, y2 — позиция, куда необходимо переместить 2го коня.
Вывод: последовательность ходов коней — (номер коня, ход)
Пример:
- 1й конь: (a1, c2)
- 2й конь: (c2, a1)
Output:
(1, b3)
(1, d4)
(2, a1)
(1, c2)
Разбор
Необходимо воспользоваться алгоритмом поиска в ширину на графе, вершины которого — возможные положения двух коней.
Для простоты реализации, вершины графа будем хранить в виде строк из двух ходов “a1c2”. Ребра графа сделаем следующего вида — первого коня можно переместить 8 способами и второго коня можно переместить 8 способами.
В алгоритме поиска в ширину при переборе ребер, исходящей из одной вершины нужно сначала рассмотреть 8 возможных ходов первого коня, потом восемь возможных ходов второго коня. Всего из каждой вершины может выходить до 16 ребер.
При восстановлении ответа получится список вершин графа, то есть список расположений двух коней. Чтобы вывести ответ в нужном формате сравним два соседних элемента списка. Если они различаются в первой вершине, значит ходил первый конь и нужно вывести число 1 и новое положение первого коня. Если они различаются во второй вершине — то ходил второй конь.
Матчасть по алгоритму поиска в ширину на графе:
Реализация
https://gist.github.com/unilecs/6a7c8f7d1fe9bf20709a96e0dd635960
