题⽬5：抓住那头⽜
总时间限制: 2000ms 内存限制: 65536kB
描述
农夫知道⼀头⽜的位置，想要抓住它。农夫和⽜都位于数轴上，农夫起始位于点N(0<=N<=100000)，
⽜位于点K(0<=K<=100000)。农夫有两种移动⽅式：
1、从X移动到X-1或X+1，每次移动花费⼀分钟
2、从X移动到2*X，每次移动花费⼀分钟
假设⽜没有意识到农夫的⾏动，站在原地不动。农夫最少要花多少时间才能抓住⽜？
#include<cstdio>
#include<algorithm>
using namespace std;
int x,y;
struct node
{
int x,times;
};
node q[3000010];
int visit[1000010];
int heads=1,last=1;
int main()
{
scanf("%d%d",&x,&y);
if(y<x)
{
printf("%d",x-y);
return 0;
}
node a;
a.x=x;a.times=0;
q[heads]=a;
while(heads<=last)
{
node n=q[heads];
heads++;
if(n.x==y)
{
printf("%d",n.times);
break;
}
node n1=n;
n1.times++;
n1.x+=1;
if(!visit[n1.x])q[++last]=n1 , visit[n1.x]=1;
n1.x-=2;
if(!visit[n1.x])q[++last]=n1 , visit[n1.x]=1;
n1.x+=1;
n1.x*=2;
if(n1.x<=100000&&!visit[n1.x])q[++last]=n1 , visit[n1.x]=1;
}
return 0;
}
哪个oj？
题目大意
约翰和奶牛都站在数轴上，一开始的时候约翰在N(O≤N≤100000)处，奶牛在K(O≤K≤100000)处。
约翰每秒可以从 x 走到 x-1，x+1，2*x 三个位置中的一个，奶牛在原地不动，那么约翰多少秒可以抓到奶牛？