Задача о перемещении шахматного коня на доске

242
04 февраля 2019, 05:20

Вводятся начальные и конечные координаты положения шахматного коня (x1[1..8], y1[1..8], x2[1..8], y2[1..8]). Нужно написать программу, определяющую за сколько ходов конь переместится в указанные координаты. Распечатать эти ходы на экране.

Пишу на языке Си. Не прошу код, но если будет, то круто. Но больше всего хочу, чтобы вы объяснили мне алгоритм решения, даже просто представить не могу, как это решается.

Не занимаюсь копипастом и т.д., я просто хочу разобраться.

Answer 1

По сути доступные ходы являются ребрами графа, а клетки - его вершинами. Кратчайший путь из одной вершины графа в другую можно найти с помощью поиска в ширину (алгоритм поиска в ширину описан многократно и найти его - не проблема).

Так что применяйте поиск в ширину, при этом сам граф можно даже не строить изначально, а только по мере работы алгоритма, когда требуется определить, куда идут ребра из данной вершины - их можно просто вычислять...

READ ALSO
Медиана уникальных элементов вектора
c++

Медиана уникальных элементов вектора

Дан вектор std::vector<std::size_t>Как наиболее эффективно получить медиану уникальных элементов вектора? Например, для вектора 1,6,3,1,5,1,2 -> 1,2,3,5,6 -> 3

 237
Почему std::regex такой медленный?
c++

Почему std::regex такой медленный?

Попробую написать регулярное выражение, которое будет разбивать строку на отдельные словаНаписал такой код:

 232
Рандомное число в промежутке A и B
c++

Рандомное число в промежутке A и B

Написал программу в которой пользователь может задать числа А и В

 236
Цикл с локатором
Java

Цикл с локатором

Имею таблицу формата:

 293