Нахождение кратчайшего пути, без использования графов Опции

[HelpAusHeaven]

Подскажите, где почитать или подскажите как осуществляется нахождения кратчайшего пути без использования графов, чистой рекурсией??

[virt]

ты скажи ,у тебя данные как хранятся?

[HelpAusHeaven]

в общем хранить их можно где угодно и как угодно... ну думаю, что хранить буду в матрице 10x10, где "0" - проход, "1" - стена, "2" - точка к которой надо найти кратчайший путь...
ну а искать его буду от 1х1 координаты...

[virt]

Код

program recursion;
const maxn=10;
var a,b:array[1..maxn,1..maxn]of integer;
   i1,j1:integer;
   i,j,n:integer;
   cou:integer;

procedure init;
begin
  readln(n);
  for i:=1 to n do
     for j:=1 to n do
        read(a[i,j]);
end;

procedure solve(i,j:integer);
begin
  if (i<1) or (i>n) or (j<1) or (j>n) or (a[i,j]=1) then exit;
  if b[i,j]>cou then b[i,j]:=cou;
  a[i,j]:=1;
  inc(cou);
  solve(i+1,j);
  solve(i-1,j);
  solve(i,j+1);
  solve(i,j-1);
  dec(cou);
end;

procedure out;
begin
  writeln(b[i1,j1]);
end;

begin
  init;
  cou:=0;
  for i:=1 to n do
     for j:=1 to n do
        b[i,j]:=maxint;
  for i:=1 to n do
     for j:=1 to n do
     if a[i,j]=2 then
        begin
           i1:=i;
           j1:=j;
        end;
  solve(1,1);
  out;
end.

Сообщение отредактировано: AlaRic - 3.05.2004 1:06

[virt]

извиняюсь ,
процедура solve должна быть такой :

Код

procedure solve(i,j:integer);
begin
  if (i<1) or (i>n) or (j<1) or (j>n) or (a[i,j]=1) then exit;
  if b[i,j]>cou then b[i,j]:=cou;
  a[i,j]:=1;
  inc(cou);
  solve(i+1,j);
  solve(i-1,j);
  solve(i,j+1);
  solve(i,j-1);
  dec(cou);
  a[i,j]:=0;{!!!!!!!!!!!!!!}
end;

Сообщение отредактировано: virt - 4.05.2004 12:19

[AlaRic]

virt теги не забывай!

[HelpAusHeaven]

virt
Спасибо большое!!!

[HelpAusHeaven]

virt
Кстати, а как он работает?
Я заполняю матрицу, где:
0 - проход
1 - стена
2 - конечный пункт прибытия

И получаю какую-то цифру 1... и матрицу b, заполненную нулями...
Путь к конечной точке имеется, причем даже не один!:)

[virt]

по идее по b находится путь (или пути) ,и она должна быть ненулевой.???
а цифра(число) это длина пути.

З.Ы. пришли плз. свою матрицу А на которой у тебя все нули (на PM)

[virt]

AlaRic
извини ,конечно ,но я хотел изменения в коде выделить.