Путь коня.

[xaero93]

Здравствуйте уважаемые.

Такую задачку задали:

Путь коня

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

Не знаю с чего начать вообще. Может кто нить направит в нужную сторону.

В файл вводится начальная позиция и кол-во ходов через пробел.

[LeBron]

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

[sergey.d]

Быстренько набросал программку, которая считает количество путей из (sr,sc) в (tr,tc) длиной stepCount на доске размером BoardSize. Результат сохраняется в pathCount. Вывод одного из путей -- попробуй самостоятельно

#include <iostream>
const int BoardSize = 8;

void horseStep(int sr, int sc, int tr, int tc, int stepCount, int &pathCount)
{
    if(sr < 0 || sr >= BoardSize || sc < 0 || sc >= BoardSize || stepCount < 0) return;
    if(sr == tr && sc == tc && stepCount == 0) { pathCount++; return; }
    horseStep(sr+2, sc-1, tr, tc, stepCount - 1, pathCount);
    horseStep(sr+2, sc+1, tr, tc, stepCount - 1, pathCount);
    horseStep(sr-2, sc-1, tr, tc, stepCount - 1, pathCount);
    horseStep(sr-2, sc+1, tr, tc, stepCount - 1, pathCount);
    horseStep(sr+1, sc+2, tr, tc, stepCount - 1, pathCount);
    horseStep(sr-1, sc+2, tr, tc, stepCount - 1, pathCount);
    horseStep(sr+1, sc-2, tr, tc, stepCount - 1, pathCount);
    horseStep(sr-1, sc-2, tr, tc, stepCount - 1, pathCount);
}

int main(int, char *[])
{
    int pathCount = 0;
    // horse jumps from (0,0) to (5,2) by 3 steps
    horseStep(0, 0, 5, 2, 3, pathCount);
    std::cout << "Exists " << pathCount << " paths" << std::endl;
    return 0;
}

Для примера ищется количество путей из (0,0) в (5,2) за три шага.

[xaero93]

Большое спасибо. С записями ходов я разберусь сам.,))
Если я правильно понял то это си (Я сам на делфи пишу)

[LeBron]

Сообщение от sergey.d

Быстренько набросал программку, которая считает количество путей из (sr,sc) в (tr,tc) длиной stepCount на доске размером BoardSize. Результат сохраняется в pathCount. Вывод одного из путей -- попробуй самостоятельно


Для примера ищется количество путей из (0,0) в (5,2) за три шага.

Да, я ступил, что классическая доска настолько маленькая, что можно писать полнейший перебор)))

Действительно, так даже проще немного. Тогда можно сократить код - не прописывать все 8 вариантов хода, а воспользоваться тем, что модуль произведения разностей координат между начальной и конечной точкой для хода коня равен двум - о перебирать все координаты двумя (или даже одним) циклами с условием.