Cod sursa(job #5434)
Utilizator | Data | 12 ianuarie 2007 14:42:29 | |
---|---|---|---|
Problema | Car | Scor | 30 |
Compilator | fpc | Status | done |
Runda | Arhiva de probleme | Marime | 9.05 kb |
const inf=2147483647;
var f:text;
a:array[0..501,0..501] of byte;
b:array[0..501,0..501,1..8] of int64;
n,m,xs,ys,xf,yf:integer;
i,j,l,gx,gy,gd:longint;
r:array[0..3] of longint;
k,c:int64;
lx,ly,ld:array[0..2000000,0..3] of integer;
begin
assign(f,'car.in');
reset(f);
readln(f,n,m);
readln(f,xs,ys,xf,yf);
if (xs=xf) and (ys=yf) then begin
close(f);
assign(f,'car.out');
rewrite(f);
writeln(f,0);
close(f);
end else
begin
for i:=1 to n do
for j:=1 to m do begin
read(f,a[i,j]);
for l:=1 to 8 do b[i,j,l]:=inf;
end;
close(f);
if n<m then for i:=0 to m+1 do begin
a[0,i]:=1;
a[n+1,i]:=1;
a[i,0]:=1;
a[i,m+1]:=1;
end
else for i:=0 to n+1 do begin
a[0,i]:=1;
a[n+1,i]:=1;
a[i,0]:=1;
a[i,m+1]:=1;
end;
for i:=1 to 8 do begin
lx[i-1,0]:=xs;
ly[i-1,0]:=ys;
ld[i-1,0]:=i;
b[xs,ys,i]:=0;
end;
r[0]:=8;
l:=0;
repeat
i:=0;
while i<r[(l mod 4)] do begin
gx:=lx[i,l mod 4];gy:=ly[i,l mod 4];gd:=ld[i,l mod 4];
{1}
if (a[gx-1,gy]=0) and (gd<>5) then
begin
c:=abs(gd-1);
if c>4 then c:=8-c;
if b[gx,gy,gd]+c<b[gx-1,gy,1] then begin
b[gx-1,gy,1]:=b[gx,gy,gd]+c;
lx[r[(l+c) mod 4],(l+c) mod 4]:=gx-1;
ly[r[(l+c) mod 4],(l+c) mod 4]:=gy;
ld[r[(l+c) mod 4],(l+c) mod 4]:=1;
inc(r[(l+c) mod 4]);
end;
end;
{2}
if (a[gx-1,gy+1]=0) and (gd<>6) then
begin
c:=abs(gd-2);
if c>4 then c:=8-c;
if b[gx,gy,gd]+c<b[gx-1,gy+1,2] then begin
b[gx-1,gy+1,2]:=b[gx,gy,gd]+c;
lx[r[(l+c) mod 4],(l+c) mod 4]:=gx-1;
ly[r[(l+c) mod 4],(l+c) mod 4]:=gy+1;
ld[r[(l+c) mod 4],(l+c) mod 4]:=2;
inc(r[(l+c) mod 4]);
end;
end;
{3}
if (a[gx,gy+1]=0) and (gd<>7) then
begin
c:=abs(gd-3);
if c>4 then c:=8-c;
if b[gx,gy,gd]+c<b[gx,gy+1,2] then begin
b[gx,gy+1,3]:=b[gx,gy,gd]+c;
lx[r[(l+c) mod 4],(l+c) mod 4]:=gx;
ly[r[(l+c) mod 4],(l+c) mod 4]:=gy+1;
ld[r[(l+c) mod 4],(l+c) mod 4]:=3;
inc(r[(l+c) mod 4]);
end;
end;
{4}
if (a[gx+1,gy+1]=0) and (gd<>8) then
begin
c:=abs(gd-4);
if c>4 then c:=8-c;
if b[gx,gy,gd]+c<b[gx+1,gy+1,4] then begin
b[gx+1,gy+1,4]:=b[gx,gy,gd]+c;
lx[r[(l+c) mod 4],(l+c) mod 4]:=gx+1;
ly[r[(l+c) mod 4],(l+c) mod 4]:=gy+1;
ld[r[(l+c) mod 4],(l+c) mod 4]:=4;
inc(r[(l+c) mod 4]);
end;
end;
{5}
if (a[gx+1,gy]=0) and (gd<>1) then
begin
c:=abs(gd-5);
if c>4 then c:=8-c;
if b[gx,gy,gd]+c<b[gx+1,gy,5] then begin
b[gx+1,gy,5]:=b[gx,gy,gd]+c;
lx[r[(l+c) mod 4],(l+c) mod 4]:=gx+1;
ly[r[(l+c) mod 4],(l+c) mod 4]:=gy;
ld[r[(l+c) mod 4],(l+c) mod 4]:=5;
inc(r[(l+c) mod 4]);
end;
end;
{6}
if (a[gx+1,gy-1]=0) and (gd<>2) then
begin
c:=abs(gd-6);
if c>4 then c:=8-c;
if b[gx,gy,gd]+c<b[gx+1,gy-1,6] then begin
b[gx+1,gy-1,6]:=b[gx,gy,gd]+c;
lx[r[(l+c) mod 4],(l+c) mod 4]:=gx+1;
ly[r[(l+c) mod 4],(l+c) mod 4]:=gy-1;
ld[r[(l+c) mod 4],(l+c) mod 4]:=6;
inc(r[(l+c) mod 4]);
end;
end;
{7}
if (a[gx,gy-1]=0) and (gd<>3) then
begin
c:=abs(gd-7);
if c>4 then c:=8-c;
if b[gx,gy,gd]+c<b[gx,gy-1,2] then begin
b[gx,gy-1,7]:=b[gx,gy,gd]+c;
lx[r[(l+c) mod 4],(l+c) mod 4]:=gx;
ly[r[(l+c) mod 4],(l+c) mod 4]:=gy-1;
ld[r[(l+c) mod 4],(l+c) mod 4]:=7;
inc(r[(l+c) mod 4]);
end;
end;
{8}
if (a[gx-1,gy-1]=0) and (gd<>4) then
begin
c:=abs(gd-8);
if c>4 then c:=8-c;
if b[gx,gy,gd]+c<b[gx-1,gy-1,8] then begin
b[gx-1,gy-1,8]:=b[gx,gy,gd]+c;
lx[r[(l+c) mod 4],(l+c) mod 4]:=gx-1;
ly[r[(l+c) mod 4],(l+c) mod 4]:=gy-1;
ld[r[(l+c) mod 4],(l+c) mod 4]:=8;
inc(r[(l+c) mod 4]);
end;
end;
inc(i);
end;
r[(l mod 4)]:=0;
inc(l);
until (r[0]=0) and (r[1]=0) and (r[2]=0) and (r[3]=0);
k:=inf;
for i:=1 to 8 do
if (b[xf,yf,i]<k) then k:=b[xf,yf,i];
assign(f,'car.out');
rewrite(f);
if k=inf then writeln(f,-1)
else writeln(f,k);
close(f);
end;
end.