记录编号	22782	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 激光电话	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.009 s
提交时间	2010-12-25 12:36:21	内存使用	0.28 MiB

{激光电话
 双向宽搜
 Author: yangbohua
 Time: 2010-12-25}

program lphone;
var
  a:array[0..101,0..101] of char;
  b,d:array[0..101,0..101] of longint;
  q:array[0..10001,1..2] of longint;
  n,m,t,h,t1,i,j,ans:longint;

function max(a,b:longint):longint;
begin
  if a>b
    then max:=a
    else max:=b;
end;

begin
  assign(input,'lphone.in');
  reset(input);
  assign(output,'lphone.out');
  rewrite(output);
  readln(m,n);
  t:=0;
  h:=0;
  for i:=1 to n do
  begin
    for j:=1 to m do
    begin
      read(a[i,j]);
      if a[i,j]='C' then
      begin
        inc(t);
        q[t,1]:=i;
        q[t,2]:=j;
        b[i,j]:=t;
      end;
    end;
    readln;
  end;
  repeat
    t1:=t;
    ans:=ans+1;
    while h<t1 do
    begin
      h:=h+1;
      i:=q[h,1];
      j:=q[h,2];
      while (i-1>0) and (a[i-1,j]<>'*') do
      begin
        i:=i-1;
        if b[i,j]>0 then
        begin
          if b[i,j]+b[i+1,j]=3 then
          begin
            if b[i+1,j]=1
              then writeln(max(0,ans*2-1-2+1))
              else writeln(max(0,ans*2-2+1));
            close(input);
            close(output);
            halt;
          end;
        end
        else
        begin
          b[i,j]:=b[i+1,j];
          inc(t);
          q[t,1]:=i;
          q[t,2]:=j;
        end;
      end;

      i:=q[h,1];
      j:=q[h,2];
      while (i+1<=n) and (a[i+1,j]<>'*') do
      begin
        i:=i+1;
        if b[i,j]>0 then
        begin
          if b[i,j]+b[i-1,j]=3 then
          begin
            if b[i-1,j]=1
              then writeln(max(0,ans*2-1-2+1))
              else writeln(max(0,ans*2-2+1));
            close(input);
            close(output);
            halt;
          end;
        end
        else
        begin
          b[i,j]:=b[i-1,j];
          inc(t);
          q[t,1]:=i;
          q[t,2]:=j;
        end;
      end;

      i:=q[h,1];
      j:=q[h,2];
      while (j+1<=m) and (a[i,j+1]<>'*') do
      begin
        j:=j+1;
        if b[i,j]>0 then
        begin
          if b[i,j]+b[i,j-1]=3 then
          begin
            if b[i,j-1]=1
              then writeln(max(0,ans*2-1-2+1))
              else writeln(max(0,ans*2-2+1));
            close(input);
            close(output);
            halt;
          end;
        end
        else
        begin
          b[i,j]:=b[i,j-1];
          inc(t);
          q[t,1]:=i;
          q[t,2]:=j;
        end;
      end;

      i:=q[h,1];
      j:=q[h,2];
      while (j-1>0) and (a[i,j-1]<>'*') do
      begin
        j:=j-1;
        if b[i,j]>0 then
        begin
          if b[i,j]+b[i,j+1]=3 then
          begin
            if b[i,j+1]=1
              then writeln(max(0,ans*2-1-2+1))
              else writeln(max(0,ans*2-2+1));
            close(input);
            close(output);
            halt;
          end;
        end
        else
        begin
          b[i,j]:=b[i,j+1];
          inc(t);
          q[t,1]:=i;
          q[t,2]:=j;
        end;
      end;
    end;

    {for i:=1 to n do
    begin
      for j:=1 to m do
        write(b[i,j],' ');
      writeln
    end;
    writeln;}
  until false;

  close(input);
  close(output);
end.