|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 15 Mar 2002 06:07:42
To : Evgeniy Jirnov
Subject : Re: Поможите pls...
--------------------------------------------------------------------------------
До меня дошли слухи, что *14.03.02* *1:18:00* пролетало сообщение
от Evgeniy к *All* про *"Поможите pls..."*. И я решил вмешаться.
EJ> Сабж. Имеется матрица(лабиринт) 50x50. 1 - стена, 0 - свободно. Hачальные
EJ> координаты практически от балды(с помощью генератора псевдослуч. чисел).
EJ> Hайти путь из начальной точки в любую точку на границе массива.
EJ> Оптимальность пути некритична, главное чтоб он был. Если пути нет, тогда
EJ> надо это как-то подсчитать. Ежели кто знает как решать подскажите
EJ> алгоритм. Исходники на C, Pas приветствуются. Спасибо за внимание.
Вообще то иногда надо эху читать, там можно найти ответ на появившийся
вопрос. Hу в вообще тут подойдет волновой алгорит(поиск в ширину), а
так же поиск в глубину. Я выбираю второе, его писать проще.
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
const
ox: array[1..4] of integer = (-1,0,1,0);
oy: array[1..4] of integer = (0,-1,0,1);
var
n: integer;
a,p: array[0..51,0..51] of shortint;
x,y: integer;
procedure init;
var i,j: integer;
begin
assign(input, 'dfs.in'); reset(input);
fillchar(a,sizeof(a),1);
read(n,x,y);
for i:= 1 to n do
for j:= 1 to n do
read(a[i,j]);
close(input);
end;
procedure dfs(x,y: integer);
var i: integer;
begin
for i:= 1 to 4 do
if(a[y+oy[i],x+ox[i]]=0)and(p[y+oy[i],x+ox[i]]=0)then
begin
p[y+oy[i],x+ox[i]]:= i;
dfs(x+ox[i],y+oy[i]);
end;
end;
procedure run;
begin
fillchar(p,sizeof(p),0);
p[x,y]:= -1;
dfs(x,y);
end;
procedure wrt(x,y: integer);
begin
if p[y,x]<>-1 then wrt(x-ox[p[y,x]],y-oy[p[y,x]]);
writeln(x,#32,y);
end;
procedure done;
begin
assign(output, 'dfs.out'); rewrite(output);
if p[1,1]=0 then writeln('no way') else wrt(1,1);
close(output);
end;
begin
init; run; done;
end.
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Metal Invaders. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
