Cod sursa(job #84616)

Utilizator gurneySachelarie Bogdan gurney Data 16 septembrie 2007 01:34:07
Problema Rj Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 3.06 kb
program rj;
  const
    fin='rj.in';
    fout='rj.out';
    nmax=200;
    ll:array[1..8] of integer=(1,1,0,-1,-1,-1,0,1);
    cc:array[1..8] of integer=(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:integer;
  pas:integer;
  old,new,xr,yr,xj,yj:integer;
  ch:char;
  viz:array[0..1,1..nmax,1..nmax] of boolean;
  l:array[0..1,0..1,0..1,0..nmax*nmax] of integer;
  lmin,cmin:integer;
  ok:boolean;
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
        for j:=1 to m do
          begin
            read(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
              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;
    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 viz[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];
                     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 viz[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];
                    viz[1,x+ll[j],y+cc[j]]:=true;
                    if viz[0,x+ll[j],y+cc[j]]=true 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.