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

[madrabbit]

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

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

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

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

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

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

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

[madrabbit]

ВОПРОС! не пойму почему не получается. 8(
вроде правильно написано.
но судя по результатам все действия просиходят на одной и той же матрице.
Хотя по идее для каждой ветки рекурсии ДОЛЖНА определяться своя матрица!
(не знаю, понятно ли объяснил)

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

Проблема в том(как я уже писал), чтобы для каждого нового дерева бралась чистая матрица!
Подскажите, в чем ошибка...

[volvo]

Хотя по идее для каждой ветки рекурсии ДОЛЖНА определяться своя матрица!

Тогда попробуй генерировать динамическую матрицу при каждом входе в рекурсию... Но вот хватит ли памяти...