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.