POJ 3278(BFS-搜索范围)

这题是BFS水的

主要是范围

0<=n,k<=100000  但是有可能搜到200000……

半天功夫才A.

program P3278;
const
   maxn=200000;
var
   n,k,i,j:longint;
   q,deep:array[1..maxn] of longint;
   b:array[0..maxn] of boolean;
procedure add(x:longint);
begin
   if not(b[x]) then
   begin
      b[x]:=true;
      inc(j);
      q[j]:=x;
      deep[j]:=deep[i]+1;
   end;
end;
begin
   read(n,k);
   i:=1;
   j:=1;
   fillchar(b,sizeof(b),false);
   b[n]:=true;
   q[1]:=n;deep[1]:=0;
   if n=k then
   begin
      writeln('0');
      halt;
   end;

   while i<=j do
   begin
      if (q[i]>0) then add(q[i]-1);
      if b[k] then break;
      if (q[i]<maxn) then add(q[i]+1);
      if b[k] then break;
      if (q[i]*2<maxn) then add(q[i]*2);
      if b[k] then break;
      inc(i);
   end;
   writeln(deep[j]);

end.