Cod sursa(job #111220)

Utilizator savimSerban Andrei Stan savim Data 28 noiembrie 2007 20:25:22
Problema Rj Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.54 kb
var lee:array [1..10000,1..2] of longint;
    v,o:array[1..4] of integer;
    c1,c2,a:array[1..100,1..100] of longint;
    min,t,r,i,j,k,p,n,m,x1,x2,y1,y2:longint;
    s:string;
    f1,f2:text;
begin
    assign(f1,'rj.in');
    assign(f2,'rj.out');
    reset(f1);
    rewrite(f2);

    readln(f1,n,m);
    for i:=1 to n do
    begin
         readln(f1,s);
         while (length(s)<m) do
               s:=s+' ';
         for j:=1 to m do
         begin
             if s[j]='X' then a[i][j]:=1
             else if s[j]=' ' then a[i][j]:=0
                  else if s[j]='R' then begin x1:=i;y1:=j;end
                       else begin x2:=i;y2:=j;end;
             c1[i][j]:=32000;
             c2[i][j]:=32000;
         end;
    end;
    v[1]:=1;v[2]:=-1;v[3]:=0;v[4]:=0;
    o[1]:=0;o[2]:=0;o[3]:=1;o[4]:=-1;

    {lee-ul pentru Romeo}
    c1[x1][y1]:=1;
    c2[x2][y2]:=0;
    k:=1;p:=0;
    lee[1][1]:=x1;
    lee[1][2]:=y1;
    while (p<k) do
    begin
         p:=p+1;
         for i:=1 to 4 do
         begin
              t:=lee[p][1]+v[i];
              r:=lee[p][2]+o[i];
              if (r>0) and (r<=n) and (t>0) and (t<=m) and (a[t][r]<>1) and
                 (c1[lee[p][1]][lee[p][2]]+1<c1[t][r]) then
                 begin
                      k:=k+1;
                      lee[k][1]:=t;
                      lee[k][2]:=r;
                      c1[t][r]:=c1[lee[p][1]][lee[p][2]]+1;
                 end;
         end;
    end;

    { lee-ul pentru Julieta}
    c1[x1][y1]:=1;
    c2[x2][y2]:=0;
    k:=1;p:=0;
    lee[1][1]:=x2;
    lee[1][2]:=y2;
    while (p<k) do
    begin
         p:=p+1;
         for i:=1 to 4 do
         begin
              t:=lee[p][1]+v[i];
              r:=lee[p][2]+o[i];
              if (r>0) and (r<=n) and (t>0) and (t<=m) and (a[t][r]<>1) and
                 (c2[lee[p][1]][lee[p][2]]+1<c2[t][r]) then
                 begin
                      k:=k+1;
                      lee[k][1]:=t;
                      lee[k][2]:=r;
                      c2[t][r]:=c2[lee[p][1]][lee[p][2]]+1;
                 end;
         end;
    end;

    min:=32000;
    for i:=1 to n do
        for j:=1 to m do
            if (c1[i][j]=c2[i][j]) and (c1[i][j]<min) then min:=c1[i][j];
    for i:=n downto 1 do
        for j:=1 to m do
            if (c1[i][j]=min) and (c1[i][j]=c2[i][j]) then
            begin
                 writeln(f2,min-1,' ',i,' ',j);
                 close(f1);
                 close(f2);
                 halt;
            end;
end.