Cod sursa(job #5434)

Utilizator fogabFodor Gabor fogab 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.