Помощь - Поиск - Пользователи - Календарь
Полная версия: прохождение лабиринта с помощью рекурсии
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Positiv
Доброго времени суток !!


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



Заранее спасибо.
hiv
Цитата(Positiv @ 22.03.2007 13:58) *
Народ , помогите пожалуйста , нужно сделать программу :
Сам чего нибудь пробовал сделать?
В принципе сложного нет ничего - просто надо в начале выйти на границу разделяющую 0,1 или границу матрицы, а потом совершать обход либо только по часовой стрелке, либо только против часовой. Если вернешся на то же место где был в начале обхода границы (так и не попав в пункт назначения), то выхода нету. Еще с самого начала можно проверить если в пункте назначения нет той цифры, на которую с самого начала встал человечек, то выхода нету.
positiv
мне надо сама процедура поиска пути , хелп
St@senk@
Ну смотри.
псевдокод
функция шаг(х,у) булен
начало
отметим, что в этой точке мы были.
если х=(длина лабиринта) и у=(ширина лабиринта), то результат = Правда, а если нет, то
если на севере свободно, то результат = шаг(х,у-1), если нет, то
если на западе свободно, то результат = шаг(х+1,у), если нет, то
если на юге свободно, то результат = шаг(х,у+1), если нет, то
если на востоке свободно, то результат = шаг(х-1,у), если нет, то
результат = ложь
конец
свободно = такая же цифра и мы там не были
если результат работы да, то тогда выход есть. А как поиск пути найти, я думаю ты догадаешься

P.S. в алгоритме не уверен.
Алена
Цитата
мне надо сама процедура поиска пути
FAQ -> Переборные алгоритмы
(чуть-чуть подкорректировать "3) задача о лабиринте")
hiv
Цитата(St@senk@ @ 22.03.2007 21:02) *
отметим, что в этой точке мы были.
если х=0 или у=0 или х=(длина лабиринта) или у=(ширина лабиринта), то результат = Правда, а если нет, то
...
P.S. в алгоритме не уверен.
Направление рассуждения абсолютно верное, но не надо отмечать был ты в той или иной точке или не был. Нужно смотреть совпадение координат с первоначальной точкой обхода, когда вышел к границе в самом начале. Более того, нужно учесть, что таких совпадений может быть несколько!
И внимательно читаем условие: "человечек , которому нужно выйти в правый нижний угол "

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

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

Код
процедура шаг
начало
если не закрашено, то начало
  закрасить
  если на севере свободно, то начало
   шаг на север
   шаг
   шаг на юг
  конец
  если на юге свободно, то начало
   шаг на юг
   шаг
   шаг на север
  конец
  если на запад свободно, то начало
   шаг на запад
   шаг
   шаг на восток
  конец
  если на востоке свободно, то начало
   шаг на восток
   шаг
   шаг на запад
  конец
конец
конец

Ну а дальше еще сюда прикрутить проверку положения
Positiv
человек может ходить только по горизонтали или по вертикали . по диагонали -нельзя. и ходить может только по тем цифрам на которой появился - то есть или по нулям или по еденицам.
St@senk@
ну тогда мой последний алгоритм должен работать...
hiv
Цитата(St@senk@ @ 23.03.2007 13:57) *
ну тогда мой последний алгоритм должен работать...
Скорее вот так он должен работать:
Код
процедура шаг
начало
если не закрашено, то начало
  закрасить
  если не дошли, то начало
    если на север можно идти и там не закрашено, то начало
     шаг на север
    конец
    если на юг можно идти и там не закрашено, то начало
     шаг на юг
    конец
    если на запад можно идти и там не закрашено, то начало
     шаг на запад
    конец
    если на восток можно идти и там не закрашено, то начало
     шаг на восток
    конец
  конец
  иначе начало
    дошли ура!
  конец
конец
конец

Но это полный перебор вариантов хождений, если матрица очень большая, то жди переполнения стека! Если матрица большая, то лучше ходить по границе.
Positiv
а где в этом алгоритме рекурсия ?
St@senk@
Hiv, нет, твой алгоритм отличается от моего smile.gif и в том псевдо коде я просто, как я уже писал не добавлял проверку местоположения.
Positiv
объясните плз подробнее , не совсем понятно , по алгоритму стасенки он вообще будет ходить по крестику !!!
Lapp
positv, чем тебя не устроила ссылка Алены?
Там все как ты просил, с рекурсией..

Если же хочешь алгоритм "правой/левой руки", то можешь взять тут:
Лабиринт
- все разложено по элементам, только без рекурсии..
St@senk@
Чтобы Ввы мне поверили, то вот реализация моего алгоритма.
Delphi

program Project2;

{$APPTYPE CONSOLE}

const n = 5;
var lab : array [1..n,1..n] of integer;
var labb : array [1..n,1..n] of boolean;
var x,y : integer;

function Step : boolean;
var res : boolean;
begin
res:=false;
if (x=n) and (y=n) then
res:=true
else begin
if not(labb[x,y]) then begin
labb[x,y]:=true;
if (y>1) and (lab[x,y-1]=lab[x,y]) then begin
dec(y);
res:=res or step;
inc(y);
end;
if (y<n) and (lab[x,y+1]=lab[x,y]) then begin
inc(y);
res:=res or step;
dec(y);
end;
if (x>1) and (lab[x-1,y]=lab[x,y]) then begin
dec(x);
res:=res or step;
inc(x);
end;
if (x<n) and (lab[x+1,y]=lab[x,y]) then begin
inc(x);
res:=res or step;
dec(x);
end;
end;
end;
step:=res;
end;

var i,j : integer;
begin
for i:= 1 to n do begin
for j:= 1 to n do begin
lab[j,i]:=random(2);
write(lab[j,i]);
labb[j,i]:=false;
end;
writeln;
end;
readln(x,y);
write(step);
readln;
end.


Pascal

program Project2;
uses crt;
const n = 5;
var lab : array [1..n,1..n] of integer;
var labb : array [1..n,1..n] of boolean;
var x,y : integer;

function Step : boolean;
var res : boolean;
begin
res:=false;
if (x=n) and (y=n) then
res:=true
else begin
if not(labb[x,y]) then begin
labb[x,y]:=true;
if (y>1) and (lab[x,y-1]=lab[x,y]) then begin
dec(y);
res:=res or step;
inc(y);
end;
if (y<n) and (lab[x,y+1]=lab[x,y]) then begin
inc(y);
res:=res or step;
dec(y);
end;
if (x>1) and (lab[x-1,y]=lab[x,y]) then begin
dec(x);
res:=res or step;
inc(x);
end;
if (x<n) and (lab[x+1,y]=lab[x,y]) then begin
inc(x);
res:=res or step;
dec(x);
end;
end;
end;
step:=res;
end;

var i,j : integer;
begin
for i:= 1 to n do begin
for j:= 1 to n do begin
lab[j,i]:=random(2);
write(lab[j,i]);
labb[j,i]:=false;
end;
writeln;
end;
readln(x,y);
write(step);
readln;
end.



Добавлено через 55 сек.
Lapp, извини, твоего сообщения не видел.
Positiv
'Lapp' . прога по ссылке алены вообще не работает =((



Lapp
Цитата(Positiv @ 24.03.2007 22:30) *

'Lapp' . прога по ссылке алены вообще не работает =((

Вот это ты зря.. sad.gif
В следующий раз, будь добр, если говоришь, что программа из форумского FAQ не работает - приведи конкретно, что именно не работает и как. Пустые утверждения, не подтвержденные фактами, не принимаются к рассмотрению вообще..
Я проверил программу - она работает. Я вставил в нее случайное задание лабиринта, как в твоем условии, все работает замечательно.
Если тебя это интересует, приведи конкретно, что у тебя не работало, и мы продолжим разговор..
Гость
когда запускаешь программу алены , так понимаю надо ввести значения , вводи вводил и ничего не произошло хоть до бесконечности вводи =((
может че то недопонял в коде ее ?
St@senk@
Там нужно сначала ввести матрицу, а потом координаты видимо ты не ввел нужное количество элементов матрицы и поэтому программа не запустилась.

Добавлено через 1 мин.
P.S. Можно не скромный вопрос? Чем мой сурс не устраивает?
Positiv
St@senk@ . надо что бы с рекурсией было , а я не знаю как в твою прогу добавить рекурсию
St@senk@
smile.gif Positiv А она там уже есть smile.gif
Код

        res:=res or step;
- Это разве не рекурсия blink.gif ?
Гость
'St@senk@' . точняк , че то я туплю дико после субботы =) . И можно к тбе еще одна просьба напиши пару комментов к своей проге та не всё понятно , не до конца по крайней мере
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.