Catch That Cow

Time Limit: 2000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

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?

输入

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

输出

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

示例输入

5 17

示例输出

4

提示

poj3278 有链接提示的题目请先去链接处提交程序，AC后提交到SDUTOJ中，以便查询存档。  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. 翻译： 老约翰的牛浪迹天涯了，老约翰想把它追回来。现在老约翰在数轴N位置上，那只特立独行的牛在K位置上。老约翰有两种方式去将牛追回来：走路和瞬移。走路：1分钟向前（x+1）或像后（X-1）移动一个位置。瞬移：一分钟内从X瞬移到2*X位置上。成功跑路的牛还沉浸在自由的喜悦中，在K位置不动了。试问，老约翰要多长时间才能将牛追回来？ 这个依旧用BFS来解决，思路和上一篇 

SDUT2139图结构练习——BFS——从起始点到目标点的最短步数差不多；

貌似dp也是可以做的；

代码如下：

<span style="font-weight: normal;"><span style="font-size:14px;">#include <bits/stdc++.h> using namespace std; int vis[100001]; int Now[100001]; int num[100001]; void BFS(int n,int m) { memset(Now,0,sizeof(Now)); memset(vis,0,sizeof(vis)); memset(num,1061109567,sizeof(num)); int ss=0,ee=0; Now[ss++]=n; vis[n]=1; num[n]=0; while(ss>ee) { int now=Now[ee++]; if(vis[now-1]==0&&(now-1)>=0&&(now-1)<=100000)//-1位置 { Now[ss++]=now-1; vis[now-1]=1; num[now-1]=num[now-1]<num[now]?num[now-1]:num[now]+1; if(now-1==m) break; } if(vis[now+1]==0&&(now+1)>=0&&(now+1)<=100000)//+1位置 { Now[ss++]=now+1; vis[now+1]=1; num[now+1]=num[now+1]<num[now]?num[now+1]:num[now]+1; if(now+1==m) break; } if(vis[now*2]==0&&(now*2)>=0&&(now*2)<=100000)//*2位置 { Now[ss++]=now*2; vis[now*2]=1; num[now*2]=num[now*2]<num[now]?num[now*2]:num[now]+1; if(now*2==m) break; } } printf("%d\n",num[m]); } int main() { int n,m; while(~scanf("%d %d",&n,&m)) { BFS(n,m); } }</span></span>