pascal 抓住那头奶牛（广度搜索）求源程序和讲解

pascal 抓住那头奶牛（广度搜索）求源程序和讲解

program catchcow;
var
a,d:array[0..200000]of longint;
st,en,i,next,t,w:longint;
find:boolean;
function direct(x,y:longint):longint;
begin
if y=1
then
direct:=x+1
else if y=2
then
direct:=x-1
else
direct:=x*2;
end;
begin
assign(input,'catchcow.in');
assign(output,'catchcow.out');
reset(input);
rewrite(output);
readln(st,en);
for i:=0 to 200000 do
a[i]:=-1;
t:=1;
w:=1;
d[1]:=st;
find:=false;
a[st]:=0;
if st=en
then
begin
find:=true;
writeln(0);
end;
while not find do
begin
for i:=1 to 3 do
begin
next:=direct(d[t],i);
if (next>=0)and(next<=200000)and(a[next]=-1)
then
begin
a[next]:=a[d[t]]+1;
if next=en
then
begin
writeln(a[next]);
find:=true;
end;
inc(w);
d[w]:=next;
end;
end;
inc(t);
end;
close(input);
close(output);
end.

其实就是用广度优先搜索，因为坐标最大100W，在内存承受的范围之内，时间也是蛮快的。
注意要判重，一个点没必要搜两次