Question

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

抓住那头奶牛题目来源:ljSAC02007公开赛(银纽),POJ题号3278
(广度搜索算法) （zznn.pas zznn.in zznn.out）
农夫约翰被告知一头逃跑奶牛的位置,想要立即抓住它,他开始在数轴的N点(0<=N<=100000),奶牛在同一个数轴的K点(0<=K<=100000).约翰有两种移动方式：1分钟内从X点移动到点X+1或X-1,在1分钟内从X点移动到点2*X.。假设奶牛没有意识到它被迫捕,根本不会移动,约翰抓住它需要多少时间?
【输入描述】
l行,两个整数N和K,用空格隔开.
【输出描述】
1行,约翰抓住奶牛所需的最少时间.
【样例输入】
5 17
【样例输出】
4

求源程序和讲解
好的我会追加悬赏

Answer 1

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，在内存承受的范围之内，时间也是蛮快的。
注意要判重，一个点没必要搜两次