首页 > 代码库 > poj 3278

poj 3278

2024-08-02 09:36:55   219人阅读

Catch That Cow
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 48376 Accepted: 15149

Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

4

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

Source

USACO 2007 Open Silver
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cstdlib>#include<cmath>#include<algorithm>#include<queue>using namespace std;int dis[100001],check[100001],n,k,minn=100001;queue<int> q;void bfs(){ 	q.push(n); 	check[n]=1; 	while(!q.empty()) 	{    int x;    x=q.front(),q.pop();    if(x==k)    minn=min(minn,dis[k]);    if(x-1>=0&&x-1<=100000&&!check[x-1])    q.push(x-1),dis[x-1]=dis[x]+1,check[x-1]=1;    if(x+1>=0&&x+1<=100000&&!check[x+1])    q.push(x+1),dis[x+1]=dis[x]+1,check[x+1]=1;    if(x*2>=0&&x*2<=100000&&!check[x*2])    q.push(x*2),dis[x*2]=dis[x]+1,check[x*2]=1;}}	    int main(){ 	memset(dis,0,sizeof(dis)); 	memset(check,0,sizeof(check)); 	scanf("%d%d",&n,&k); 	bfs(); 	printf("%d\n",minn); 	return 0;}

　　

poj 3278


联系
我们