Cod sursa(job #57985)

Utilizator gurneySachelarie Bogdan gurney Data 3 mai 2007 19:56:16
Problema Car Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 3.65 kb
program car;
const
  fin='car.in';
  fout='car.out';
  nmax=500;
  inf=maxlongint shr 1;
  di:array[0..7] of longint=(1,1,0,-1,-1,-1,0,1);
  dj:array[0..7] of longint=(0,1,1,1,0,-1,-1,-1);
type
  list=array[1..nmax*nmax] of longint;

var
  d:array[0..nmax+1,0..nmax+1,0..7] of longint;
  a:array[0..2] of list;
  lst:array[0..2] of longint;
  ult:array[0..2] of longint;
  p:array[0..2] of longint;
  q,aux:list;
  dir,i,j,k,m,n,x,y,xi,yi,xf,yf:longint;

function code(i,j,dir:longint):longint;
  begin
    code:=(i shl 9)+j+(dir shl 18);
  end;

function pi(x:longint):longint;
  begin
    pi:=(x shr 9) and 511;
  end;

function pj(x:longint):longint;
  begin
    pj:=x and 511;
  end;

function pd(x:longint):longint;
  begin
    pd:=x shr 18;
  end;

procedure insert(x,l:longint);
  begin
    inc(ult[l]);
    a[l,ult[l]]:=x;
  end;

procedure expand(x:longint;l:longint);
  var
    i,j,dir,xx,dd:longint;
  begin
    i:=pi(x);j:=pj(x);dir:=pd(x);
    if l=0 then
      begin
        if d[i,j,dir]+l<d[i+di[dir],j+dj[dir],dir] then
          begin
            d[i+di[dir],j+dj[dir],dir]:=d[i,j,dir]+l;
            insert(code(i+di[dir],j+dj[dir],dir),(y+l)mod 3);
          end;
      end
    else if l=1 then
      begin
        dd:=(dir+1)and 7;
        if d[i,j,dir]+l<d[i+di[dd],j+dj[dd],dd] then
          begin
            d[i+di[dd],j+dj[dd],dd]:=d[i,j,dir]+l;
            insert(code(i+di[dd],j+dj[dd],dd),(y+l)mod 3);
          end;
        dd:=(dir+7)and 7;
        if d[i,j,dir]+l<d[i+di[dd],j+dj[dd],dir] then
          begin
            d[i+di[dd],j+dj[dd],dd]:=d[i,j,dir]+l;
            insert(code(i+di[dd],j+dj[dd],dd),(y+l)mod 3);
          end;
      end
    else if l=2 then
      begin
        dd:=(dir+2)and 7;
        if d[i,j,dir]+l<d[i+di[dd],j+dj[dd],dd] then
          begin
            d[i+di[dd],j+dj[dd],dd]:=d[i,j,dir]+l;
            insert(code(i+di[dd],j+dj[dd],dd),(y+l)mod 3);
          end;
        dd:=(dir+6)and 7;
        if d[i,j,dir]+l<d[i+di[dd],j+dj[dd],dd] then
          begin
            d[i+di[dd],j+dj[dd],dd]:=d[i,j,dir]+l;
            insert(code(i+di[dd],j+dj[dd],dd),(y+l)mod 3);
          end;
      end;
  end;

begin
  assign(input,fin);
    reset(input);
    readln(n,m);
    readln(xi,yi,xf,yf);
    for i:=1 to n do
      begin
        for j:=1 to m do
          begin
            read(x);
            for k:=0 to 7 do
            if x=1 then
              d[i,j,k]:=-1
            else
              d[i,j,k]:=inf;
          end;
      end;
    //border
    for i:=0 to m+1 do
      for j:=0 to 7 do
      begin
        d[0,i,j]:=-1;
        d[n+1,i,j]:=-1;
      end;
    for i:=0 to n+1 do
      for j:=0 to 7 do
      begin
        d[i,0,j]:=-1;
        d[i,m+1,j]:=-1;
      end;

  close(input);
  assign(output,fout);
    rewrite(output);
    lst[0]:=1;lst[1]:=1;lst[2]:=1;
    ult[0]:=0;ult[1]:=0;ult[2]:=0;
    for dir:=0 to 7 do
      begin
        if d[xi+di[dir],yi+dj[dir],0]<>-1 then
          begin
            insert(code(xi+di[dir],yi+dj[dir],dir),0);
            d[xi+di[dir],yi+dj[dir],dir]:=0;
          end;
      end;
    k:=0;
    while (lst[0]<=ult[0]) or ((lst[1]<=ult[1]) or (lst[2]<=ult[2])) do
      begin
        y:=k mod 3;
        i:=1;
        while i<=ult[y] do
          begin
            for dir:=0 to 2 do
              expand(a[y,i],dir);
            inc(i);
          end;
        lst[y]:=1;ult[y]:=0;
        inc(k);
      end;
    k:=-1;
    for i:=0 to 7 do
      if d[xf,yf,i]<>inf then
        if d[xf,yf,i]>k then
          k:=d[xf,yf,i];
    writeln(k);
  close(output);
end.