Cod sursa(job #78856)

Utilizator floringh06Florin Ghesu floringh06 Data 19 august 2007 22:19:31
Problema Rj Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 6.8 kb
type  pozitie=record  lin,col:byte;
          end;
 var a                :array[0..101,0..101] of char;
     c                :array[0..100000] of pozitie;
     leer,leej        :array[0..101,0..101] of integer;
     pc,pu,inr,inj,aux:pozitie;
     i,j,n,m,k        :integer;
     first,last       :longint;
     fin,fout         :text;
     interm           :string[120];
     date             :pozitie;
     min              :longint;

 procedure qin(p:pozitie);
    begin
      c[last]:=p;
      inc(last);
    end;

 procedure qout(var aux:pozitie);
    begin
      aux:=c[first];
      inc(first);
    end;

 function isemty:boolean;
       begin
         if first=last then isemty:=true
            else isemty:=false;
       end;

  begin
    assign(fin,'rj.in'); reset(fin);
    read(fin,n,m);
    readln(fin);
    for i:=1 to n do
     begin
      interm:='';
      read(fin,interm);
//      writeln(interm);
      readln(fin);
      for j:=1 to m do
       begin
        a[i,j]:=interm[j];
        if a[i,j]='R' then
                     begin
                       inr.lin:=i;
                       inr.col:=j;
                     end;
        if a[i,j]='J' then
                     begin
                       inj.lin:=i;
                       inj.col:=j;
                     end;
       end;
    end;

    for i:=1 to n do
      for j:=1 to m do
        leer[i,j]:=20000;

    for i:=1 to n do
      for j:=1 to m do
        leej[i,j]:=20000;
    first := 0; last := 0;
    qin(inj); leej[inj.lin,inj.col]:=0;

    while not(isemty) do
       begin
         qout(aux);
         pc:=aux;
     {1}    pu.lin:=pc.lin-1;   pu.col:=pc.col-1;
         if a[pu.lin,pu.col]=' ' then
           if leej[pu.lin,pu.col]>leej[pc.lin,pc.col]+1 then
             begin
              leej[pu.lin,pu.col]:=leej[pc.lin,pc.col]+1;
              qin(pu);
             end;

     {2}    pu.lin:=pc.lin-1;   pu.col:=pc.col;
         if a[pu.lin,pu.col]=' ' then
           if leej[pu.lin,pu.col]>leej[pc.lin,pc.col]+1 then
             begin
              leej[pu.lin,pu.col]:=leej[pc.lin,pc.col]+1;
              qin(pu);
             end;
     {3}    pu.lin:=pc.lin-1;   pu.col:=pc.col+1;
         if a[pu.lin,pu.col]=' ' then
           if leej[pu.lin,pu.col]>leej[pc.lin,pc.col]+1 then
             begin
              leej[pu.lin,pu.col]:=leej[pc.lin,pc.col]+1;
              qin(pu);
             end;
     {4}    pu.lin:=pc.lin;   pu.col:=pc.col+1;
         if a[pu.lin,pu.col]=' ' then
           if leej[pu.lin,pu.col]>leej[pc.lin,pc.col]+1 then
             begin
              leej[pu.lin,pu.col]:=leej[pc.lin,pc.col]+1;
              qin(pu);
             end;
     {5}   pu.lin:=pc.lin+1;   pu.col:=pc.col+1;
         if a[pu.lin,pu.col]=' ' then
           if leej[pu.lin,pu.col]>leej[pc.lin,pc.col]+1 then
             begin
              leej[pu.lin,pu.col]:=leej[pc.lin,pc.col]+1;
              qin(pu);
             end;
     {6}    pu.lin:=pc.lin+1;   pu.col:=pc.col;
         if a[pu.lin,pu.col]=' ' then
           if leej[pu.lin,pu.col]>leej[pc.lin,pc.col]+1 then
             begin
              leej[pu.lin,pu.col]:=leej[pc.lin,pc.col]+1;
              qin(pu);
             end;
     {7}    pu.lin:=pc.lin+1;   pu.col:=pc.col-1;
         if a[pu.lin,pu.col] =' ' then
           if leej[pu.lin,pu.col]>leej[pc.lin,pc.col]+1 then
             begin
              leej[pu.lin,pu.col]:=leej[pc.lin,pc.col]+1;
              qin(pu);
             end;
      {8}   pu.lin:=pc.lin;   pu.col:=pc.col-1;
         if a[pu.lin,pu.col]=' ' then
           if leej[pu.lin,pu.col]>leej[pc.lin,pc.col]+1 then
             begin
              leej[pu.lin,pu.col]:=leej[pc.lin,pc.col]+1;
              qin(pu);
             end;
      end;


    qin(inr); leer[inr.lin,inr.col]:=0;

    while not(isemty) do
       begin
         qout(aux);
         pc:=aux;
     {1}    pu.lin:=pc.lin-1;   pu.col:=pc.col-1;
         if a[pu.lin,pu.col]=' ' then
           if leer[pu.lin,pu.col]>leer[pc.lin,pc.col]+1 then
             begin
              leer[pu.lin,pu.col]:=leer[pc.lin,pc.col]+1;
              qin(pu);
             end;

     {2}    pu.lin:=pc.lin-1;   pu.col:=pc.col;
         if a[pu.lin,pu.col]=' ' then
           if leer[pu.lin,pu.col]>leer[pc.lin,pc.col]+1 then
             begin
              leer[pu.lin,pu.col]:=leer[pc.lin,pc.col]+1;
              qin(pu);
             end;
     {3}    pu.lin:=pc.lin-1;   pu.col:=pc.col+1;
         if a[pu.lin,pu.col]=' ' then
           if leer[pu.lin,pu.col]>leer[pc.lin,pc.col]+1 then
             begin
              leer[pu.lin,pu.col]:=leer[pc.lin,pc.col]+1;
              qin(pu);
             end;
     {4}    pu.lin:=pc.lin;   pu.col:=pc.col+1;
         if a[pu.lin,pu.col]=' ' then
           if leer[pu.lin,pu.col]>leer[pc.lin,pc.col]+1 then
             begin
              leer[pu.lin,pu.col]:=leer[pc.lin,pc.col]+1;
              qin(pu);
             end;
     {5}   pu.lin:=pc.lin+1;   pu.col:=pc.col+1;
         if a[pu.lin,pu.col]=' ' then
           if leer[pu.lin,pu.col]>leer[pc.lin,pc.col]+1 then
             begin
              leer[pu.lin,pu.col]:=leer[pc.lin,pc.col]+1;
              qin(pu);
             end;
     {6}    pu.lin:=pc.lin+1;   pu.col:=pc.col;
         if a[pu.lin,pu.col]=' ' then
           if leer[pu.lin,pu.col]>leer[pc.lin,pc.col]+1 then
             begin
              leer[pu.lin,pu.col]:=leer[pc.lin,pc.col]+1;
              qin(pu);
             end;
     {7}    pu.lin:=pc.lin+1;   pu.col:=pc.col-1;
         if a[pu.lin,pu.col]=' ' then
           if leer[pu.lin,pu.col]>leer[pc.lin,pc.col]+1 then
             begin
              leer[pu.lin,pu.col]:=leer[pc.lin,pc.col]+1;
              qin(pu);
             end;
      {8}   pu.lin:=pc.lin;   pu.col:=pc.col-1;
         if a[pu.lin,pu.col]=' ' then
           if leer[pu.lin,pu.col]>leer[pc.lin,pc.col]+1 then
             begin
              leer[pu.lin,pu.col]:=leer[pc.lin,pc.col]+1;
              qin(pu);
             end;
      end;
assign(fout,'rj.out'); rewrite(fout);
{for i:=1 to n do
  begin
    for j:=1 to m do
     write(fout,leej[i,j]:7);
     writeln(fout);
  end;
writeln(fout);
for i:=1 to n do
  begin
    for j:=1 to m do
     write(fout,leer[i,j]:7);
     writeln(fout);
  end;}
// writeln(leer[5,52],' ',leej[5,52]);
 min:=maxlongint;
 for i:=1 to n do
   for j:=1 to m do
      begin
        if leej[i,j]=leer[i,j] then
           if leej[i,j]<min then
                             begin
                               min:=leej[i,j];
                               date.lin:=i;
                               date.col:=j;
                             end;
      end;

 writeln(fout,min+1,' ',date.lin,' ',date.col);
 close(fin);
 close(fout);
end.