прохождение лабиринта с помощью рекурсии, бинарная матрица Опции

[Positiv]

Доброго времени суток !!


Народ , помогите пожалуйста , нужно сделать программу :
дана двоичная матрица из 0 и 1 , в рандомной позиции появлятся человечек , которому нужно выйти в правый нижний угол , идти он может только по тем цифрам , на котрой сначала появился (то есть если появился на 1 то только по еденицам). Если выхода нет то нужно вывести на экран что нет выхода . матрица задается рандомно.
Программа должна быть сделана при помощи рекурсии .



Заранее спасибо.

[St@senk@]

Ну смотри.
псевдокод
функция шаг(х,у) булен
начало
отметим, что в этой точке мы были.
если х=(длина лабиринта) и у=(ширина лабиринта), то результат = Правда, а если нет, то
если на севере свободно, то результат = шаг(х,у-1), если нет, то
если на западе свободно, то результат = шаг(х+1,у), если нет, то
если на юге свободно, то результат = шаг(х,у+1), если нет, то
если на востоке свободно, то результат = шаг(х-1,у), если нет, то
результат = ложь
конец
свободно = такая же цифра и мы там не были
если результат работы да, то тогда выход есть. А как поиск пути найти, я думаю ты догадаешься

P.S. в алгоритме не уверен.

Сообщение отредактировано: St@senk@ - 23.03.2007 11:32

[hiv]

отметим, что в этой точке мы были.
если х=0 или у=0 или х=(длина лабиринта) или у=(ширина лабиринта), то результат = Правда, а если нет, то
...
P.S. в алгоритме не уверен.

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

ЗЫ: Просьба к автору темы - поподробней опишите как человечек может ходить?

ДА! Совсем забыл... у человечика должно быть "направление движения" и его все время должно тянуть в какую-то сторону (или по часовой, или против). Т.е. использовать абсолютные понятия север, восток, юг и запад нельзя.

Сообщение отредактировано: hiv - 23.03.2007 9:35