ЛЮДИ ОТКЛИКНИТЕСЬ!!! Помогите пожалуйста с задачей. Не могу написать его на паскале. Имеется алгоритм
Матрица размера N*M определяет некоторый лабиринт. B матице элемент 1 обозначает стену, а 0 определяет свободное место. В первой строке матрицы определяются входы x(i), а в последней выходы y(i), i=1,..,k, которые должны быть нулевыми элементами.
Необходимо определить, можно ли
а) провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза.
б) то же, но человека можно выводить чеpез любой из выходов. Примечание: Движение в лабиринте осуществляется только по вертикали или горизонтали.
Алгоритм:
Основная стратегия человека, вошедшего в самый левый вход, состоит в прохождении лабиринта, используя наиболее левые свободные места лабиринта, т.е. он должен двигаться, держась правой рукой за "стенку" лабиринта. Этот процесс можно формализовать следующим образом. Находясь в очередной позиции лабиринта, он должен помнить, с какой стороны он пришел сюда (слева, справа, сверху, снизу), и, руководствуясь этой информацией, вобрать следующее наиболее предпочтительное направление в новую позицию (куда он может пойти и где еще не был). При этом удобно использовать стек, в верхушке которого находятся координаты текущей позиции и направление, по которому в нее пришли. При этом все посещенные клетки метятся. Легко заметить, что если в позицию попали сверху, то наилучшим направлением будет налево, затем вниз, направо, и наконец назад (вверх). Аналогично можно определить наилучшие направления для других случаев.
Эта стратегия повторяется каждым из людей, при этом позиции, помеченные предыдущими людьми, считаются запрещенными для следующих.
Возможно, это тебе поможет:
http://tpxexe.narod.ru/020.html
Спасибо!! Это хоть что-то! Но мне по заданию нужно провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза.
К сожалению, я больше ничего подсказать не в силах..
Задачка меня заинтересовала - я вообще питаю слабость к лабиринтам..
Сначала - видимо, у тебя опечатка:
1101111110111111111011111111101111111111
1101111110111111111011111111100011111111
1101111100111000100011111110111011111111
1101110001111010101111111110000011111111
1101110011111010100000011111101111111111
1101111001111010111111011111101110000011
1101111101111010111111011100000000111011
1101111101111010000000011101111101111011
1101111100000011111111111101111100000011
1101111100011000000011111101111111111111
1101111111111000000000111100000111111111
1100011111000000000011111111110111111111
1111000000011100000111110000000000000111
1111011111000000111111110111111101110111
1111011111011110111000000000000001110111
1111000000011110000011101101111100000111
1111111111011111111110001101111111111111
1111111111011111111110111100000111111111
1111111111011111100000111111110111111111
1111111111011111101111111111110111111111
uses
CRT;
const
mx=100; nx=100;
Left=1; Right=-1;
Trace=-1;
type
tLabyrinth=array[0..mx,0..nx]of integer;
var
m,n,m1,n1,x,y,dx,dy,k,l,x0,i,j:integer;
Lab:tLabyrinth;
f:text;
c:char;
procedure Show;
var
i,j:integer;
begin
for j:=0 to n1 do begin
for i:=0 to m1 do begin
l:=Lab[i,j];
if l>0 then begin
TextColor(l+7);
Write('*');
TextColor(7)
end
else if l=0 then Write(' ')
else Write('#');
end;
WriteLn
end
end;
procedure Turn(dir:integer; var x,y:integer);
var
z:integer;
begin
z:=x;
x:=dir*y;
y:=-dir*z
end;
procedure Step(var x,y,dx,dy:integer);
begin
Turn(Left,dx,dy);
while Lab[x+dx,y+dy]>0 do Turn(Right,dx,dy);
x:=x+dx;
y:=y+dy
end;
begin
{Read the data file}
Assign(f,'labyrinth_0_0.dat');
ReSet(f);
m1:=-1;
while not EoLn(f) do begin
Read(f,c);
Inc(m1);
case c of
'1',' ': Lab[m1,0]:=1;
'0': Lab[m1,0]:=0
end
end;
ReadLn(f);
n1:=0;
while not EoF(f) do begin
Inc(n1);
for i:=0 to m1 do begin
Read(f,c);
case c of
'1',' ': Lab[i,n1]:=1;
'0': Lab[i,n1]:=0
end
end;
ReadLn(f)
end;
m:=m1-1; n:=n1-1;
Close(f);
{Passing}
k:=0;
WriteLn('Labyrinth ',m,'x',n);
{Probing all the entries}
for x0:=m downto 1 do if Lab[x0,0]=0 then begin
Inc(k);
x:=x0;
y:=1;
dx:=0;
dy:=1;
while (y>0)and(y<n1) do begin
Inc(Lab[x,y],Trace);
Step (x,y,dx,dy);
end;
Write('Entry ',k,': ');
if y=0 then WriteLn('No way!') else WriteLn('Passed.');
for j:=1 to n do for i:=1 to m do if Lab[i,j]<0 then Lab[i,j]:=k+1;
Show;
Write('Press Enter..');
ReadLn;
WriteLn
end;
WriteLn('Done.')
end.
Большое спасибо!!!
Lapp, гениально