Алгоритмічно відстань між двома клітинами можна отримати наступним чином. Беремо початкову клітку (рівень 0). Відзначаємо всі клітини на відстані одного ходу коня. Отримуємо клітини рівня 1. Повторюємо цю процедуру для всіх клітин рівня 1 - отримуємо клітини рівня 2 і т.д. поки все клітини не будуть відзначені.
Перечитую і продумую всі ще раз. Якщо скласти алгоритм для визначення найменшої кількості ходів. Задавши клітинці а1 координати (0; 0), а 2 відповідно (0; 1), клітинці b1 - (1; 0) і так далі. І починаючи з клітинки (0; 0) як наведено вище визначаємо за скільки ходів можна дістатися до кожної клітинки. Ходів може бути від одного до шести. Якщо рух здійснювати між клітинами різного кольору, то відстань непарне, якщо між клітинами одного кольору, то парне.
Ще введемо одне визначення, що зміщенням будемо вважати твір різниць відповідних координат. Визначимо зміщення для клітинок різного кольору:
досяжні за один хід: 2
досяжні за три ходи: 0; 4; 6; 10; 12; 20
досяжні за п'ять ходів: 0; 14; 28; 42
Тепер для клітинок однакового кольору
досяжні за 2 ходу: 0; 3; 8; 9
досяжні за 4 ходи: 0; 1; 4; 5; 7; 12; 15; 16; 21; 24; 25; 35; 36
досяжні за 6 ходів: 49
Зауважимо, що в першому і другому випадках повторюється тільки нуль. Для цього введемо ще одне визначення сума - сума координат клітини (зауважимо що для чорних клітинок вона парна, для білих непарна)
Тепер сам алгоритм:
1) Знаходимо суми клітинок, початкової і кінцевої і зміщення.
2) Якщо суми однакової парності, то
досяжні за 2 ходу: 0; 3; 8; 9
досяжні за 4 ходи: 0; 1; 4; 5; 7; 12; 15; 16; 21; 24; 25; 35; 36
досяжні за 6 ходів: 49
Якщо різного кольору, то
досяжні за один хід: 2
досяжні за три ходи: 0; 4; 6; 10; 12; 20
досяжні за п'ять ходів: 0; 14; 28; 42
3) Якщо зсув дорівнює 0, то розглядаємо суму кінцевої точки:
Якщо 2 або 4, то два ходу
Якщо 1; 3 або 5, то три ходи
Якщо 6, то 4 ходи
Якщо 7, то 5 ходів.
Обчисліть d (С5; g8)
с - 2, g - 6. Отже точки (2, 4), (6, 7)
1) суми клітинок 6 і 13, отже вони різного кольору. Зсув (6-2) х (7-4) = 12.
2) виходячи з цього
різного кольору:
досяжні за один хід: 2
досяжні за три ходи: 0; 4; 6; 10; 12; 20
досяжні за п'ять ходів: 0; 14; 28; 42
Робимо висновок, що відстань між клітинами одно 3
Шановні форумчани, будь ласка скажіть, чи можна що-небудь з цього витягти? Або це маячня?