Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Теоретические вопросы _ Нахождение кратчайшего пути
Автор: HelpAusHeaven 1.05.2004 20:39
Подскажите, где почитать или подскажите как осуществляется нахождения кратчайшего пути без использования графов, чистой рекурсией??
Автор: virt 1.05.2004 21:23
ты скажи ,у тебя данные как хранятся?
Автор: HelpAusHeaven 2.05.2004 6:21
в общем хранить их можно где угодно и как угодно... ну думаю, что хранить буду в матрице 10x10, где "0" - проход, "1" - стена, "2" - точка к которой надо найти кратчайший путь...
ну а искать его буду от 1х1 координаты...
Автор: virt 3.05.2004 0:56
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.
Автор: virt 3.05.2004 15:30
извиняюсь ,
процедура 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;
Автор: AlaRic 3.05.2004 23:11
virt теги не забывай!
Автор: HelpAusHeaven 3.05.2004 23:48
virt
Спасибо большое!!!
Автор: HelpAusHeaven 4.05.2004 3:07
virt
Кстати, а как он работает?
Я заполняю матрицу, где:
0 - проход
1 - стена
2 - конечный пункт прибытия
И получаю какую-то цифру 1... и матрицу b, заполненную нулями...
Путь к конечной точке имеется, причем даже не один!:)
Автор: virt 4.05.2004 12:16
по идее по b находится путь (или пути) ,и она должна быть ненулевой.???
а цифра(число) это длина пути.
З.Ы. пришли плз. свою матрицу А на которой у тебя все нули (на PM)
Автор: virt 4.05.2004 12:17
AlaRic
извини ,конечно ,но я хотел изменения в коде выделить.