MLASERP - Laser Phones

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=101;
  di:array[1..4] of longint=(-1,1,0,0);
  dj:array[1..4] of longint=(0,0,-1,1);
  dh:array[1..4] of longint=(0,0,1,1);
  oo=1000001;
var
  f1,f2:text;
  m,n,hsize,startu,startv,targetu,targetv:longint;
  a:array[1..MAXN,1..MAXN] of char;
  hpos,d:array[1..MAXN,1..MAXN,0..1] of longint;
  hu,hv,ht:array[1..MAXN*MAXN*2] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1);
  close(f2);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure inp;
var
  i,j:longint;
begin
  readln(f1,n,m);
  for i:=1 to m do
    begin
      for j:=1 to n do
        begin
          read(f1,a[i,j]);
          if a[i,j]='C' then
            if startu=0 then begin startu:=i; startv:=j; end
            else begin targetu:=i; targetv:=j; end;
        end;
      readln(f1);
    end;
end;
procedure downHeap(i:longint);
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (d[hu[j+1],hv[j+1],ht[j+1]]<d[hu[j],hv[j],ht[j]]) then inc(j);
      if (d[hu[j],hv[j],ht[j]]<d[hu[i],hv[i],ht[i]]) then
        begin
          swap(hpos[hu[i],hv[i],ht[i]],hpos[hu[j],hv[j],ht[j]]);
          swap(hu[i],hu[j]);
          swap(hv[i],hv[j]);
          swap(ht[i],ht[j]);
        end;
      i:=j; j:=i<<1;
    end;
end;
procedure upHeap(i:longint);
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (d[hu[i],hv[i],ht[i]]<d[hu[j],hv[j],ht[j]]) do
    begin
      swap(hpos[hu[i],hv[i],ht[i]],hpos[hu[j],hv[j],ht[j]]);
      swap(hu[i],hu[j]);
      swap(hv[i],hv[j]);
      swap(ht[i],ht[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push(u,v,t:longint);
begin
  inc(hsize);
  hu[hsize]:=u;
  hv[hsize]:=v;
  ht[hsize]:=t;
  hpos[u,v,t]:=hsize;
  upHeap(hsize);
end;
procedure pop(var u,v,t:longint);
begin
  u:=hu[1]; v:=hv[1]; t:=ht[1];
  hpos[u,v,t]:=0;
  swap(hu[1],hu[hsize]);
  swap(hv[1],hv[hsize]);
  swap(ht[1],ht[hsize]);
  hpos[hu[1],hv[1],ht[1]]:=1;
  dec(hsize); downHeap(1);
end;
procedure solve;
var
  huong,u,v,t,uu,vv,tt:longint;
begin
  for u:=1 to m do
  for v:=1 to n do
  for t:=0 to 1 do
    d[u,v,t]:=oo;
  u:=startu; v:=startv;
  hsize:=0; d[u,v,0]:=0; d[u,v,1]:=0;
  push(u,v,0); push(u,v,1);
  while hsize>0 do
    begin
      pop(u,v,t);
      if (u=targetu) and (v=targetv) then
        begin
          writeln(f2,d[u,v,t]);
          exit;
        end;
      for huong:=1 to 4 do
        begin
          uu:=u+di[huong]; vv:=v+dj[huong]; tt:=dh[huong];
          if (uu>0) and (vv>0) and (uu<=m) and (vv<=n) and (a[uu,vv]<>'*') then
            begin
              if (t=tt) and (d[uu,vv,tt]>d[u,v,t]) then
                begin
                  d[uu,vv,tt]:=d[u,v,t];
                  if hpos[uu,vv,tt]=0 then push(uu,vv,tt)
                  else upHeap(hpos[uu,vv,tt]);
                end;
              if (t<>tt) and (d[uu,vv,tt]>d[u,v,t]+1) then
                begin
                  d[uu,vv,tt]:=d[u,v,t]+1;
                  if hpos[uu,vv,tt]=0 then push(uu,vv,tt)
                  else upHeap(hpos[uu,vv,tt]);
                end;
            end;
        end;
    end;
end;
begin
  openF;
  inp;
  solve;
  closeF;
end.

Download