рекурсивная работа с матрицей, задачка с шахматным конем Опции

[madrabbit]

Здравствуйте.
Помогите пожалуйста с алгоритмом. хотя бы просто на пальцах или отправьте к соответствующим ссылкам.
Интересует следующий алгоритм:

Предположим задана некоторая матрица размерности N на N( положим поле больше шахматной доски), а также
координаты двух точек(элементы массива a[i,j], b[i1,j1]),

Задача. Найти оптимальный путь межды этими точками "шахматным конем".

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

посоветуйте принцип решения.
каким способом, например, можно оборвать вложенную процедуру при приближении к краям поля. Ну и вообще... задач однотипных я знаю много.
Интересует сам принцип и средства решения.
Хотелось бы самому дойти, но видно опыта самоучки маловато...

спасибо вам заранее за помощь! :molitva:

Сообщение отредактировано: madrabbit - 18.12.2004 17:53

[APAL]

проблема в том, каким конкретно способом обрывать процедуру(каким оператором)

Обрывать принудительно не надо - закончить процедуру если мы попали на 2-ку или некуда ходить (т.е. все возможные варианты хода уже имеют "1").

куда заносить последовательность ходов,в отдельный массив? для каждой последовательности свой массив определять? для меня проблематично.

Вот здесь надо подумать как реализовать хранение результатов....
Например запись в файл/файлы или в динамическую память (это быстрее), а потом только сделать поиск... а можно уже при работе искать короткий путь, т.е. увеличивать счетчик для следующей итерации - если достигнут финал (2), то проверяем предидущий результат и если он хуже - запоминаем текущий.