Cod sursa(job #84780)

Utilizator gurneySachelarie Bogdan gurney Data 17 septembrie 2007 00:11:55
Problema Rj Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 3.3 kb
program rj;
  const
    fin='rj.in';
    fout='rj.out';
    nmax=200;
    ll:array[1..8] of longint=(1,1,0,-1,-1,-1,0,1);
    cc:array[1..8] of longint=(0,1,1,1,0,-1,-1,-1);
var
  a:array[0..nmax+1,0..nmax+1] of boolean;
  i,j,k,m,n,x,y:longint;
  pas:longint;
  old,new,xr,yr,xj,yj:longint;
  ch:char;
  viz2,viz:array[0..1,0..nmax+1,0..nmax+1] of boolean;
  l:array[0..1,0..1,0..1,0..nmax*nmax] of longint;
  lmin,cmin:longint;
  ok:boolean;
  s:string;
begin
  assign(input,fin);
    reset(input);
    readln(n,m);
    //border
    for i:=0 to n+1 do
      begin
        a[i,0]:=true;
        a[i,m+1]:=true;
      end;
    for j:=0 to m+1 do
      begin
        a[0,j]:=true;
        a[n+1,j]:=true;
      end;
    //
    for i:=1 to n do
      begin
        read(s);
        for j:=1 to m do
          begin
            if length(s)>=j then
              ch:=s[j]
            else
              ch:=' ';
            if ch=' ' then
              a[i,j]:=false
            else if ch='X' then
              a[i,j]:=true
            else if ch='R' then
              begin
                xr:=i;yr:=j;
                a[i,j]:=false;
              end
            else if ch='J' then
              begin
                xj:=i;yj:=j;
                a[i,j]:=false;
              end;
          end;
        readln;
      end;
  close(input);
  assign(output,fout);
    rewrite(output);
    pas:=1;
    old:=0;new:=1;
    l[0,new,0,0]:=1;
    l[0,new,0,1]:=xj;l[0,new,1,1]:=yj;
    l[1,new,0,0]:=1;
    l[1,new,0,1]:=xr;l[1,new,1,1]:=yr;
    lmin:=300;cmin:=300;
    ok:=false;
    while not(ok) do
      begin
        inc(pas);
        fillchar(viz,sizeof(viz),false);
        old:=new;new:=old xor 1;
        l[0,new,0,0]:=0;l[1,new,0,0]:=0;
        for i:=1 to l[0,old,0,0] do
          begin
            x:=l[0,old,0,i];y:=l[0,old,1,i];
            for j:=1 to 8 do
              if a[x+ll[j],y+cc[j]]=false then
                if viz2[0,x+ll[j],y+cc[j]]=false then
                   begin
                     inc(l[0,new,0,0]);
                     l[0,new,0,l[0,new,0,0]]:=x+ll[j];
                     l[0,new,1,l[0,new,0,0]]:=y+cc[j];
                     viz2[0,x+ll[j],y+cc[j]]:=true;
                     viz[0,x+ll[j],y+cc[j]]:=true;
                   end;
          end;
        for i:=1 to l[1,old,0,0] do
          begin
            x:=l[1,old,0,i];y:=l[1,old,1,i];
            for j:=1 to 8 do
              if a[x+ll[j],y+cc[j]]=false then
                if viz2[1,x+ll[j],y+cc[j]]=false then
                  begin
                    inc(l[1,new,0,0]);
                    l[1,new,0,l[1,new,0,0]]:=x+ll[j];
                    l[1,new,1,l[1,new,0,0]]:=y+cc[j];
                    viz2[1,x+ll[j],y+cc[j]]:=true;
                    viz[1,x+ll[j],y+cc[j]]:=true;
                    if viz[0,x+ll[j],y+cc[j]] then
                      begin
                        if (x+ll[j]<lmin)or((x+ll[j]=lmin)and(y+cc[j]<cmin)) then
                          begin
                            lmin:=x+ll[j];
                            cmin:=y+cc[j];
                          end;
                        ok:=true;
                      end;
                  end;
          end;
      end;
    writeln(pas,' ',lmin,' ',cmin);
  close(output);
end.