3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
|
1 | |
Лабиринт из массива09.10.2008, 23:40. Показов 7738. Ответов 11
Метки нет (Все метки)
Вот есть такая задача:
Код
Лабиринт задан матрицей a(m,n), состоящей из 0 и 1, причем а[1,1]=0 и a[m,n]=0. Разработать рекурсивную процедуру нахождения пути из клетки а[1,1] в a[m,n]. Путь должен состоять из элементов, равных 0. Ходить можно только по вертикалям и горизонталям Мне просто нужно допридумывать идею, проверку в начале, ну и ещё придумать что-бы это "начальная" проверка не мешала основной работе функции, т.к. мне надо через рекурсию писать, а это означает что придётся заново вызывать эту же функцию...Если у вас появились идеи отпишитесь плз, а то мне всё больше начинает казатся, что "правило правой(левой) руки" здесь плохо применимо и есть что-то ещё, попроще, а может быть и посложнее...
0
|
09.10.2008, 23:40 | |
Ответы с готовыми решениями:
11
Игра лабиринт. ИИ в лабиринте. Как задать лабиринт Лабиринт 3D лабиринт Лабиринт |
0 / 0 / 0
Регистрация: 09.10.2008
Сообщений: 18
|
||||||
10.10.2008, 00:16 | 2 | |||||
Это недоделаная программа подобного типа.
Сдесь стены лабиринта = 1 а проход 0 (как у тя ток наоборот ) посмотри код сам, я спать ппц хочу. Программа не работает так как я ее не доделал. Но функции передвежения (Move) и проверки местоположения (Chek (не финишь ли это)) написаны вроде правильно
0
|
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
|
10.10.2008, 00:22 [ТС] | 3 |
Ну у меня как-бы и есть стены "1", а проход "0", ну и во 2-ых, я тока недавно начал изучать языки программирования и в C++ не шарю, да и как я вижу, у тебя проверки как-то не так проходят...у меня тут появилась мысль насчёт того что делать с
0
|
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
|
12.10.2008, 22:32 [ТС] | 4 |
Помогите закончить...
Код
Program laba11b; type stil=array[0..100,0..100] of byte; Var a:stil; i,j,m,n,b:integer; Procedure lab(i,j:integer;b:integer); begin If (i=m) and (j=n) then writeln('KoHeL/') else begin if b=1 then if a[i+1,j]=0 then {!! BnpaBO !!} begin Writeln('---> A[' ,i+1, ',' ,j, ']'); b:=1; lab(i+1,j,b); end; if a[i,j+1]=0 then {!! BnpaBO !!} begin Writeln('---> A[' ,i, ',' ,j+1, ']'); b:=1; lab(i,j+1,b); end else b:=-1; if b=-1 then if a[i-1,j]=0 then {!! BleBO !!} begin Writeln('----> A[' ,i-1, ',' ,j, ']'); b:=-1; lab(i-1,j,b); end; if a[i,j+1]=0 then {!! BleBO !!} begin Writeln('----> A[' ,i, ',' ,j+1, ']'); b:=-1; lab(i,j+1,b); end else b:=0; if b=0 then if a[i,j-1]=0 then {!! Bhu3 !!} begin Writeln('----> A[' ,i, ',' ,j-1, ']'); b:=0; lab(i,j-1,b); end; if a[i+1,j]=0 then {!! Bhu3 !! } begin Writeln('----> A[' ,i+1, ',' ,j, ']'); b:=0; lab(i+1,j,b); end else b:=2; if b=2 then if a[i,j+1]=0 then {!! BBePx !!} begin Writeln('----> A[' ,i, ',' ,j-1, ']'); b:=2; lab(i,j-1,b); end; if a[i-1,j]=0 then {!! BBePx !! } begin Writeln('----> A[' ,i+1, ',' ,j, ']'); b:=2; lab(i+1,j,b); end else b:=1; end; end; begin Writeln('BBeDUte pa3MePHotb matPuL/bl mxn'); Write('m='); readln(m); Write('n='); readln(n); for i:=1 to m do for j:=1 to n do begin Write('A[' ,i, ',' ,j, ']='); Readln(a[i,j]); end; for i:=0 to m+1 do begin a[i,0]:=1; a[i,n+1]:=1; end; for j:=1 to n+1 do begin a[0,j]:=1; a[m+1,j]:=1; end; for i:=0 to m+1 do begin Writeln; for j:=0 to n+1 do Write(a[i,j]); end; readln; b:=1; lab(1,1,b); Readln; end.
0
|
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
12.10.2008, 23:20 | 5 |
Неправильно выход из рекурсии. Надо так:
Код
Procedure lab(i,j:integer;b:integer); begin If (i=m) and (j=n) then begin writeln('KoHeL/'); readln; halt; end else Код
for j:=[B][I][COLOR="Red"]1[/COLOR][/I][/B] to n+1 do begin a[0,j]:=1; a[m+1,j]:=1; end;
0
|
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
|
12.10.2008, 23:28 [ТС] | 6 |
Спасибо за советы, но прога всё равно не работает, у меня иссякли мысли...
0
|
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
13.10.2008, 07:42 | 7 |
Сейчас потестировал программу, дело в том что она работает при n=m и при m>n. Когда столбцов больше чем строк, не работает. Проверьте сами, Вы скорее найдете ошибку. На всякий случай моя программа, которая на 2/3 работает.
0
|
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
|
14.10.2008, 03:44 [ТС] | 8 |
Хотел бы вас поправить немного, программа не работает, когда происходят определённые повороты в лабиринте, все их описывать не вижу смысла, просто их не так много, сейчас переделываю программу полностью, уменьшая объём и дорабатывая её на ходу, надеюсь сегодня к утру, может быть завтра к вечеру закончу...
0
|
0 / 0 / 0
Регистрация: 23.10.2008
Сообщений: 6
|
|
23.10.2008, 20:28 | 9 |
Всем привет!
Мне такую же задачу дали. Можете помочь с кодом и алгоритмом. написать нужно на С. Я новичок. Спасибо!
0
|
10 / 10 / 2
Регистрация: 18.08.2008
Сообщений: 127
|
|
25.10.2008, 20:05 | 10 |
по борабану на каком языке писать .
надо составить новмальный алгоритм програму и все буде пучком. 1) 1- стена ; 0 - проход : 2- обрамляющая рамка лабиринта если при анализе вылезит 2 - то это конец лабиринта- выход 2) анализировать надо не по правилу рук а про правилу часов сначала свободна ли верхняя клетка . если не то правая ... нижняя левая . разумется там надо учитывать был ли ты раньше в этой клетке .
0
|
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
|
25.10.2008, 20:29 [ТС] | 11 |
Не полностью согласен, т.к. а если мы попали на перекрёсток?Ну что-то типа токого
Код
0001111 1101101 1000001 1011111 1000000
0
|
10 / 10 / 2
Регистрация: 18.08.2008
Сообщений: 127
|
|
26.10.2008, 20:51 | 12 |
не совсем !
первое что надо учитывать это вход на перекресток. черепашка может двигаться в четырех направлениях вверх , вправо , влево и вниз. Так пусть есть переменная Dv (движение)и X,Y позиции. Dv будет равнo в зависимости от направления 1,2,3,4. Теперь надо найти верное следующее направление Dv2. Возможных вариантов тоже будет 4 . нельзя не учитывать движение обратно . Там может быть карман ( апендекс). вычислять это движение разумеется тоже в определенном порядке . если Dv=1 то Dv2= 2,3,4,1 Dv=2 то Dv2= 3,4,1.2 Dv=3 то Dv2= 4,1,2,3 Dv=4 то Dv2= 1,2,3,4 естественно что бы облегчить код и анализ лучше ввести X1 и Y1 аналитические приращения которые будут равны при Dv2=1 X1=0 Y1=-1 Dv2=1 X1=0 Y1=-1 Dv2=2 X1=1 Y1=0 Dv2=3 X1=0 Y1=1 Dv2=4 X1=-1 Y1=0 Теперь можно легко вычислить нужную клетку то есть найти клетку равную 0 свободную в поле М спросив М(X+X1,Y+Y2) если она равна нулю то сделать движение Dv=Dv2; X=X+X1;Y=Y+Y1 если это вход (=2) или выход(=3) то соответственно сделать выход из программы если (=1) то это стенка Увеличить Dv2 на единицу .если Dv2=5 то сделать =1 кстати четвертое приращение Dv2 заставить черешку пятиться , а обратный ход свободен . Если же вы решили отмечать трассу(значением 4),то при анализе хода считать ,что это 0. Еще данный алгоритм работает при ширине туннеля 1 или 2 .Еще шире не ручаюсь за результат . Так как алгоритм анализирует соседние клетки (а они должны быть). то поле должно быть окружено границей из 1 или программно их поставив расширив размеры исходного поля на 2 .
0
|
26.10.2008, 20:51 | |
26.10.2008, 20:51 | |
Помогаю со студенческими работами здесь
12
Лабиринт Лабиринт с++ лабиринт Лабиринт C++ Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |