задача заключается вот в чем,лабиринт это двумерный массив символом 12x12 '.'-это пустая клетка. '#'-стена

char x[12][12]={{'#','#','#','#','#','#','#','#','#','#','#','#'},{'#','.','.','.','#','.','.','.','.','.','.','#'},{'.','.','#','.','#','.','#','#','#','#','.','#'},{'#','#','#','.','#','.','.','.','.','#','.','#'},{'#','.','.','.','.','#','#','#','.','#','.','.'},{'#','#','#','#','.','#','.','#','.','#','.','#'},{'#','.','.','#','.','#','.','#','.','#','.','#'},{'#','#','.','#','.','#','.','#','.','#','.','#'},{'#','.','.','.','.','.','.','.','.','#','.','#'},{'#','#','#','#','#','#','.','#','#','#','.','#'},{'#','.','.','.','.','.','.','#','.','.','.','#'},{'#','#','#','#','#','#','#','#','#','#','#','#',}};        

это уже готовый лабиринт.
нужно построить рекурсивную функцию нахождения пути из лабиринта,двигаться всегда надо касаясь правой рукой стены.
мои соображения
x[y][z] -может иметь лишь 4 возможных вариаций
x[--y][z]
x[++y][z]
x[y][++z]
x[y][--z]

только как реализовать рекурсивную функцию используя это в голову не приложу,а самое главное,я не могу понять как выйти из такого рода рекурсивной функции когда работал с числами возвращалась единица,а что возвращать при работе с символами непонятно

Это сообщение отредактировал(а) ShadowC - 24.10.2011, 18:14

я бы сказал x[y-1][z], x[y+1][z] и т.д.

1. определить, не находимся ли мы в выходе, т.е. если наши координаты либо 0 либо максимальное значение (11)
2. если нет, определить следующий допустимый шаг (y1, z1), т.е. рассмотреть последовательно варианты y+1, z+1, y-1, z-1. след. шаг допустим, если в новой позиции точка
3. вызвать себя рекурсивно с параметрами y1, z1

Это сообщение отредактировал(а) newbee - 24.10.2011, 18:25

а как у тебя определяется куда должно быть совершено движение? и как у тебя определяется конечная позиция?


Это сообщение отредактировал(а) ShadowC - 24.10.2011, 18:28

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

Функции may_move_* определяют, можно ли из заданной точки двигаться в одну из сторон, то есть в реализации например may_move_right должна стоять проверка, не является ли символ справа от текущей позиции решеткой. is_finish определят, находится символ ли в текущей позиции в конце лабиринта, можешь в качестве конца использовать '$' и сверяться с ним, например.

Это сообщение отредактировал(а) newbee - 24.10.2011, 18:42

обьясни пожалуйста еще вот это

pos(pos.x-1,pos.y) дело в том что я с таким синтаксисом не знаком

ShadowC, это псевдокод. Функция принимает текущую точку pos, которая характеризуется двумя координатами x и y. И далее она вызывает себя же с новой сдвинутой в одну из четырех сторон точкой.

Ну, например:

Так нельзя - зациклишься.
Если делать перебор, начиная движения вниз, то:
1. делаем движение вниз;
2. попадаем в тупик; вызвращаемся вверх;
3. теперь опять путь вниз свободен -  движемся вниз; ...

При движении по правилу правой руки программируется примерно так:

Но и в этом случае возможны зацикливания - если в лабиринте есть внунтенние циклы.

издиваешься? в условии задачи 1 функция котоая принимает двумерный массив и отправную точку и все

надо еще текущее направление хранить, иначе непонятно куда поворачивать

http://codepad.org/hXSmuTj8
писал наспех, но идея думаю понятна

Ну я о том и говорю - в классе position есть поле angle - если не устраивает решение с классами, разверните классы в обычные функции и будет вам счастье.

в том-то и прикол что по условию задания должна быть 1 функция,я думаю это не просто так...

ShadowC, теперь с условием выхода прояснилось?

да так-то оно понятно,остается невыполненным одно условие задачи,которое я думаю там нелишнее,функция должна быть одна и принимать отправную точку и массив 12-12,я думаю вся сложность в выполнение именно этого условия

а что в моем примере не так? массив и точка передается в параметрах

я полагаю точка это не координаты,а сама точка тоесть в данном примере x[2][0] ну и у тебя 2 функции

Можно рекурсию свернуть в цикл, принт реализовать внутри функции - и будет одна функция.


Добавлено через 5 минут и 4 секунды
Если не нравится начальную точку передавать координатами в параметрах - можно передать крестиком на карте лабиринта.
Тогда надо в начале функции добавить цикл по поиску крестика. Будет один параметр - карта лабиринта

вторая функция (print) к алгоритму отношения не имеет, ее можно просто выбросить. к тому же она вызывается лишь раз, ее тело можно встроить в функцию maze. 


я всегда думал, что точка характеризуется координатами, а не тем, что в ней находится. например клетка на шахматной доске определяется координатами а не цветом (цвета всего 2, клеток 64). 
если дело в количестве аргументов функции, заведите struct Point { int y, z; };

можно и так
но это имхо параноидальное решение)))))

ShadowC, кажется Вы слишком придираетесь)))) А как ведь начиналось:

math64, baldina, имхо вы делаете человеку медвежью услугу. Суть передали, зачем досконально код писать, пусть сам думает. Думать - полезно.

Так что, получилась одна функция или нет?

Проще написать код - чем описать как он работает. В моём коде есть ошибки - я его не запускал даже на компиляцию, пусть ищет, пишет комментарии.

Моск у всех по-разному устроен. Не всегда то, что одному очевидно, является простым для другого.
Бывает, что на анализ предоставленного кода человек тратит значительные усилия, а сам написать вообще не может.

Мы не сразу код начали писать.

Добавлено через 4 минуты и 36 секунд
моей первой книгой в области информатики были "Алгоритмы и структуры данных" Н.Вирта. тогда это была чуть ли не единственная книга про алгоритмы в магазине.
при первом прочтении я ничего не понял. при втором понял все. при третьем осознал, что во второй все понял неправильно.