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

[madrabbit]

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

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

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

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

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

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

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

[madrabbit]

но можно...

Если на пальцах:

1. Для начальной позиции ищем все возможности хода.
2. Для каждой такой возможности рекурсивно вызываем ту же процедуру поиска возможностей хода.

Замечания:
ИМХО: место куда надо попасть лучше отметить, например "2"
Ставить единицы туда куда походили и не затирая старые единица. Это чтобы наша процедура поиска вариантов хода "не ходила" на одну клетку дважды.
Теперь только организовать запись найденных вариантов и произвести поиск никратчашего/-их.

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

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