Доброго времени суток !!
Народ , помогите пожалуйста , нужно сделать программу :
дана двоичная матрица из 0 и 1 , в рандомной позиции появлятся человечек , которому нужно выйти в правый нижний угол , идти он может только по тем цифрам , на котрой сначала появился (то есть если появился на 1 то только по еденицам). Если выхода нет то нужно вывести на экран что нет выхода . матрица задается рандомно.
Программа должна быть сделана при помощи рекурсии .
Заранее спасибо.
мне надо сама процедура поиска пути , хелп
Ну смотри.
псевдокод
функция шаг(х,у) булен
начало
отметим, что в этой точке мы были.
если х=(длина лабиринта) и у=(ширина лабиринта), то результат = Правда, а если нет, то
если на севере свободно, то результат = шаг(х,у-1), если нет, то
если на западе свободно, то результат = шаг(х+1,у), если нет, то
если на юге свободно, то результат = шаг(х,у+1), если нет, то
если на востоке свободно, то результат = шаг(х-1,у), если нет, то
результат = ложь
конец
свободно = такая же цифра и мы там не были
если результат работы да, то тогда выход есть. А как поиск пути найти, я думаю ты догадаешься
P.S. в алгоритме не уверен.
ну тогда, алгоритм, который проходит через все доступные точки.
пусть закрасить = поднять буленовское значение в этой токе в Правда
человек может ходить только по горизонтали или по вертикали . по диагонали -нельзя. и ходить может только по тем цифрам на которой появился - то есть или по нулям или по еденицам.
ну тогда мой последний алгоритм должен работать...
а где в этом алгоритме рекурсия ?
Hiv, нет, твой алгоритм отличается от моего и в том псевдо коде я просто, как я уже писал не добавлял проверку местоположения.
объясните плз подробнее , не совсем понятно , по алгоритму стасенки он вообще будет ходить по крестику !!!
positv, чем тебя не устроила ссылка Алены?
Там все как ты просил, с рекурсией..
Если же хочешь алгоритм "правой/левой руки", то можешь взять тут:
http://forum.pascal.net.ru/index.php?s=&showtopic=16264&view=findpost&p=95245
- все разложено по элементам, только без рекурсии..
Чтобы Ввы мне поверили, то вот реализация моего алгоритма.
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.
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.
'Lapp' . прога по ссылке алены вообще не работает =((
когда запускаешь программу алены , так понимаю надо ввести значения , вводи вводил и ничего не произошло хоть до бесконечности вводи =((
может че то недопонял в коде ее ?
Там нужно сначала ввести матрицу, а потом координаты видимо ты не ввел нужное количество элементов матрицы и поэтому программа не запустилась.
Добавлено через 1 мин.
P.S. Можно не скромный вопрос? Чем мой сурс не устраивает?
St@senk@ . надо что бы с рекурсией было , а я не знаю как в твою прогу добавить рекурсию
Positiv А она там уже есть
'St@senk@' . точняк , че то я туплю дико после субботы =) . И можно к тбе еще одна просьба напиши пару комментов к своей проге та не всё понятно , не до конца по крайней мере