|
{ Бэк-трекинг: Проход по лабиринту }
{ Есть матрица n:m, состоящая из 0 и 1. 1 - это стенка, 0 - проход. }
{ Надо найти оптимальный проход из точки is,js (нчаало) в точку ie, je }
{ (конец). }
{ }
{ Входной файл LAB.IN содержит: }
{ 1-я строка - размер поля }
{ 2-я строка - координаты начальной позиции (row,col) }
{ 3-я строка - координаты конечной позиции (row,col) }
{ 4-я строка и далее - схему лабиринта из 0 и 1 }
{ Например: }
{ 10 10 }
{ 2 10 }
{ 1 6 }
{ 1 1 1 1 1 0 1 1 1 1 }
{ 1 0 0 0 0 0 1 0 1 0 }
{ 1 0 1 1 1 1 1 0 1 0 }
{ 1 0 1 0 1 0 0 0 1 0 }
{ 1 0 1 0 1 0 0 0 1 0 }
{ 0 0 1 0 1 0 0 0 1 0 }
{ 0 0 1 0 1 1 1 1 1 0 }
{ 1 0 0 1 0 1 0 0 0 0 }
{ 1 1 0 0 0 0 0 1 0 0 }
{ 1 1 1 1 1 1 1 1 1 1 }
{ }
{ Выходной файл LAB.OUT содержит маршрут прохода (i1:j1 ... in:jn): }
{ 1:10 }
{ 2:10 }
{ 3:10 }
{ .... }
{--------------------------------------------------------------------------}
const LN = 50; LM = 50;
var a:array[1..LN,1..LM] of byte;
p:array[1..LN*LM,1..2] of byte;
s:array[1..LN*LM,1..2] of byte;
n,m,si,sj,ei,ej,index,min:integer;
procedure INIT;
var i,j:integer;
begin
assign(input,'lab.in'); reset(input);
assign(output,'lab.out'); rewrite(output);
readln(n,m);
readln(si,sj);
readln(ei,ej);
for i:=1 to n do begin
for j:=1 to n-1 do begin
read(a[i,j]);
end;
readln(a[i,n]);
end;
index:=0; min:=ln*lm;
end;
procedure Store;
begin
if (min > index) then begin
move( p, s, sizeof(p) );
min:=index;
end;
end;
procedure DONE;
var i:integer;
begin
for i:=1 to min do writeln(s[i,1],':',s[i,2]);
end;
procedure FindPath(i,j:integer);
begin
a[i,j]:=2;
inc(index);
p[index,1]:=i; p[index,2]:=j;
if (i=ei) and (j=ej) then begin
Store;
end else begin
if (i > 1) and (a[i-1,j]=0) then FindPath(i-1,j);
if (i < n) and (a[i+1,j]=0) then FindPath(i+1,j);
if (j > 1) and (a[i,j-1]=0) then FindPath(i,j-1);
if (j < m) and (a[i,j+1]=0) then FindPath(i,j+1);
end;
dec(index);
a[i,j]:=0;
end;
begin
INIT;
FindPath(si,sj);
DONE;
end.
| |