Cod sursa(job #113783)

Utilizator ionescu88alex ionescu ionescu88 Data 11 decembrie 2007 15:32:53
Problema Rj Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 4.21 kb
type patrat=record
       x,y:byte;
     end;
type pelem=^elem;
     elem=record
       info:patrat;
       next:pelem;
     end;
var fi,fo:text;
    a:array[0..105,0..105]of integer;
    o:array[0..105,0..105]of integer;
    n,m,i,j,iu,ju,mini,minj:integer;
    min:integer;
    first,last:pelem;
    linie:string;
    pc,pu,romeo,julieta:patrat;
procedure qin(vl:patrat);
var x:pelem;
begin
  new(x);
  x^.info:=vl; x^.next:=nil;
  if first=nil then
    begin
      first:=x; last:=first; exit; end;
  last^.next:=x;
  last:=x;
end;
procedure qout(var vl:patrat);
var x:pelem;
begin
  vl:=first^.info;
  x:=first;
  first:=first^.next;
  dispose(x);
end;
procedure verif;
begin
  if o[iu,ju]<min then
    begin
      mini:=iu; minj:=ju; min:=o[iu,ju]; end;
  if o[iu,ju]=min then
    if ju<minj then
      begin
        mini:=iu; minj:=ju; min:=o[iu,ju]; end;
end;
begin
  assign(fi,'rj.in'); reset(fi);
  assign(fo,'rj.out'); rewrite(fo);
  readln(fi,n,m); min:=maxint;
  for i:=1 to n do
    begin
      readln(fi,linie);
      for j:=1 to length(linie) do
        begin
          if linie[j]='R' then
            begin
              romeo.x:=i;
              romeo.y:=j;
              a[i,j]:=0;
            end;
          if linie[j]='J' then
            begin
              julieta.x:=i;
              julieta.y:=j;
              a[i,j]:=0;
            end;
          if linie[j]='X' then a[i,j]:=1;
          if linie[j]=' ' then a[i,j]:=0;
          o[i,j]:=11000;
        end;
    end;
    for i:=0 to n+1 do
      begin
        o[i,0]:=11000; o[i,n+1]:=11000; end;
    for i:=0 to m+1 do
      begin
        o[0,i]:=11000; o[m+1,i]:=11000; end;
    o[julieta.x,julieta.y]:=1; o[romeo.x,romeo.y]:=1;
    qin(julieta);
    qin(romeo);
    while first<>nil do
      begin
        qout(pc); i:=pc.x; j:=pc.y;
        iu:=i+1; ju:=j;
        if (iu<=n)and(j<=m) then begin
        if (a[iu,ju]=0)and(o[i,j]+1=o[iu,ju]) then verif;
        if (a[iu,ju]=0)and(o[i,j]+1<o[iu,ju]) then
          begin
            o[iu,ju]:=o[i,j]+1;
            pu.x:=iu; pu.y:=ju; qin(pu);
          end; end;
        iu:=i-1; ju:=j;
        if (iu>0)and(ju<=m) then begin
        if (a[iu,ju]=0)and(o[i,j]+1=o[iu,ju]) then verif;
        if (a[iu,ju]=0)and(o[i,j]+1<o[iu,ju]) then
          begin
            o[iu,ju]:=o[i,j]+1;
            pu.x:=iu; pu.y:=ju; qin(pu);
          end; end;
        iu:=i; ju:=j+1;
        if (ju<=m)and(iu<=n) then begin
        if (a[iu,ju]=0)and(o[i,j]+1=o[iu,ju]) then verif;
        if (a[iu,ju]=0)and(o[i,j]+1<o[iu,ju]) then
          begin
            o[iu,ju]:=o[i,j]+1;
            pu.x:=iu; pu.y:=ju; qin(pu);
          end; end;
        iu:=i; ju:=j-1;
        if (ju>0)and(iu<=n) then begin
        if (a[iu,ju]=0)and(o[i,j]+1=o[iu,ju]) then verif;
        if (a[iu,ju]=0)and(o[i,j]+1<o[iu,ju]) then
          begin
            o[iu,ju]:=o[i,j]+1;
            pu.x:=iu; pu.y:=ju; qin(pu);
          end; end;
        iu:=i+1; ju:=j+1;
        if (iu<=n)and(ju<=m) then begin
        if (a[iu,ju]=0)and(o[i,j]+1=o[iu,ju]) then verif;
        if (a[iu,ju]=0)and(o[i,j]+1<o[iu,ju]) then
          begin
            o[iu,ju]:=o[i,j]+1;
            pu.x:=iu; pu.y:=ju; qin(pu);
          end; end;
        iu:=i-1; ju:=j-1;
        if (iu>0)and(ju>0) then begin
        if (a[iu,ju]=0)and(o[i,j]+1=o[iu,ju]) then verif;
        if (a[iu,ju]=0)and(o[i,j]+1<o[iu,ju]) then
          begin
            o[iu,ju]:=o[i,j]+1;
            pu.x:=iu; pu.y:=ju; qin(pu);
          end; end;
        iu:=i+1; ju:=j-1;
        if (iu<=n)and(ju>0) then begin
        if (a[iu,ju]=0)and(o[i,j]+1=o[iu,ju]) then verif;
        if (a[iu,ju]=0)and(o[i,j]+1<o[iu,ju]) then
          begin
            o[iu,ju]:=o[i,j]+1;
            pu.x:=iu; pu.y:=ju; qin(pu);
          end; end;
        iu:=i-1; ju:=j+1;
        if (iu>0)and(ju<=m) then begin
        if (a[iu,ju]=0)and(o[i,j]+1=o[iu,ju]) then verif;
        if (a[iu,ju]=0)and(o[i,j]+1<o[iu,ju]) then
          begin
            o[iu,ju]:=o[i,j]+1;
            pu.x:=iu; pu.y:=ju; qin(pu);
          end; end;
      end;
    write(fo,min,' ',mini,' ',minj);
    close(fi);
    close(fo);
end.