Как рассчитать кратчайшие шаги для этих шахмат

Question

Китайские шахматы имеют 8 * 8 = 64 ячейки. И точка (1,1), (1,2) .... (8,8).

И конь ходит по диагональной линии двух ячеек от точки он включен.

Вычислить самый короткий шаг (ы) между двумя точками для лошади ходить. Например

(1,1) до (4,4). Лошадь идет следующим образом (1,1)> (2,3)> (4,4) 2 этапа

Китайские шахматы, закон законный ! [Введите описание изображения здесь] [1]

Answer 1

проверить алгоритм Брешенема. это хороший алгоритм для этой задачи

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Answer 2

1. создать Integer board[8][8]
2. установить начальную точку в 0.
3. найдены все точки, где лошадь может двигаться от начальной точки и установите его в 1.
4. для всех точек, установленных на 1, найти все незастроенные точки, где лошадь может переместиться от них и установить ее на 2.
5. повторите этот алгоритм до тех пор, пока не будет установлена ​​конечная точка. Число в конечной точке - это количество шагов.

Если вы хотите, чтобы получить путь, который вы должны идти от конечной точки до начальной точки в этой плате:

1. в конечной точке содержит N.
2. найти точку, где лошадь может двигаться от конца и содержит N-1.
3. повторите, пока не достигнете начальной точки.
4. верните этот путь.

Answer 3

Вы можете превратить шахматную доску в виде графика, то вы можете использовать алгоритм поиска пути, как Дейкстры: