Cod sursa(job #335326)

Utilizator 05_YohnE1 La5c01 05_Yohn Data 29 iulie 2009 15:43:05
Problema Car Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.79 kb
type shh=record
     xx,yy,pp:integer;
     end;
const oriz:array[1..8]of shortint=(-1,0,1,1,1,0,-1,-1);
      vert:array[1..8]of shortint=(-1,-1,-1,0,1,1,1,0);
var v:array[1..50,1..50]of 0..1;
cost:array[1..50,1..50]of longint;
c:array[1..2000]of shh;
i,j,p,n,m,u,xnou,ynou,x,y,x1,x2,y1,y2,poz,nou,cc:longint;
begin
assign(input,'car.in');reset(input);
assign(output,'car.out');rewrite(output);
read(n,m);
read(x1,y1,x2,y2);
for i:=1 to n do
    for j:=1 to m do begin
        read(v[i,j]);
        cost[i,j]:=1000000;
    end;
u:=0;
for i:=1 to 8 do begin
    xnou:=x1+oriz[i];
    ynou:=y1+vert[i];
    if (xnou in [1..n])and(ynou in [1..m])and(v[xnou,ynou]=0) then begin
       inc(u);
       c[u].xx:=xnou; c[u].yy:=ynou; c[u].pp:=i;
       cost[xnou,ynou]:=0;
    end;
end;
p:=1;
while p<=u do begin
      x:=c[p].xx; y:=c[p].yy; poz:=c[p].pp;
      xnou:=x+oriz[poz]; ynou:=y+vert[poz]; cc:=cost[x,y];
      if (xnou in [1..n])and(ynou in [1..m])and(v[xnou,ynou]=0)
      and(cc<=cost[xnou,ynou]) then
      begin
            inc(u);
            c[u].xx:=xnou; c[u].yy:=ynou; c[u].pp:=poz;
            cost[xnou,ynou]:=cost[x,y];
      end;
         for i:=-2 to 2 do if i<>0 then begin
             nou:=poz+i;
             if nou<1 then nou:=nou+8;
             if nou>8 then nou:=nou-8;
             xnou:=x+oriz[nou]; ynou:=y+vert[nou];
             cc:=cost[x,y]+abs(i);
             if (xnou in [1..n])and
                (ynou in [1..m])and
                (cc<=cost[xnou,ynou])and
                (v[xnou,ynou]=0) then
                begin
                inc(u);
                c[u].xx:=xnou; c[u].yy:=ynou; c[u].pp:=nou;
                cost[xnou,ynou]:=cc;
                end;
         end;
      inc(p);
end;
writeln(cost[x2,y2]);
close(output);
end.