codevs 3060 抓住那头奶牛
USACO
时间限制: 1 s
空间限制: 16000 KB
题目等级 : 黄金 Gold
题目描述 Description
农夫约翰被告知一头逃跑奶牛的位置，想要立即抓住它，他开始在数轴的N 点（0≤N≤100000），奶牛在同一个数轴的K 点（0≤K≤100000）。约翰有两种移动方式：1 分钟内从x 点移动到x+1 或x-1；1 分钟内从x 点移动到2x。假设奶牛不会移动，约翰抓住它需要多少时间？
输入描述 Input Description
一行两个整数N 和K，用空格隔开。
输出描述 Output Description
约翰抓住它需要的最少时间。
样例输入 Sample Input
5 17
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
见题目
/*借助这道题目再练习一下双向广搜*/
#include<iostream>
using namespace std;
#define N 200100
#include<cstdio>
int visit[N];
int dis[N]={};
#include<queue>
struct poi{
int x,tim,flag;
};
int n,k;
int bfs()
{
queue<poi>que;
visit[n]=;visit[k]=;
dis[n]=;dis[k]=;
que.push(poi{n,,});
que.push(poi{k,,});
while(!que.empty())
{
poi now=que.front();
que.pop();
if(now.x->=&&!visit[now.x-])
{
visit[now.x-]=now.flag;
dis[now.x-]=now.tim+;
que.push(poi{now.x-,now.tim+,now.flag});
}
else if(visit[now.x-]&&now.flag!=visit[now.x-])
{
return dis[now.x-]++now.tim;
}
if(now.x+<=(N/)&&!visit[now.x+])
{
visit[now.x+]=now.flag;
dis[now.x+]=now.tim+;
que.push(poi{now.x+,now.tim+,now.flag});
}
else if(visit[now.x+]&&now.flag!=visit[now.x+])
{
return dis[now.x+]++now.tim;
}
if(now.x*<=(N/)&&!visit[now.x*])
{
visit[now.x*]=now.flag;
dis[now.x*]=now.tim+;
que.push(poi{now.x*,now.tim+,now.flag});
}
else if(visit[now.x*]&&now.flag!=visit[now.x*])
{
return dis[now.x*]++now.tim;
}
}
}
int main()
{
scanf("%d%d",&n,&k);
cout<<bfs()<<endl;
return ;
}