题目
总时间限制: 2000ms 内存限制: 65536kB
描述
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入
两个整数，N和K
输出
一个整数，农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
题意
农夫起始位置为N，牛的位置为K，输入为N和K，农夫每分钟可以向左或向右移动一步（从X到X-1或X+1），或者将当前位置翻倍（从X到2*X），每次移动花费一分钟，输出最少分钟数。
思路
用深度优先搜索+递归，从牛的位置K开始向农夫的位置N查找。如果农夫位置N大于牛位置K，通过每次后退一步的方式（花费N-K分钟）；否则，从K位置开始，通过三种操作反向思考：当K为奇数时，+1或-1，当K为偶数时，/2（对应农夫的*2）
代码
#include<bits/stdc++.h>
using namespace std;
int n,k,ans;
void d(int x,int y,int sum){//递归函数，x是农夫位置，y是牛位置，sum是已花费时间if(ans<=sum) return;//如果当前时间已经超过已知最小时间，返回ans=min(ans,sum+abs(y-x));//更新最短时间为当前时间加上走到牛的位置的时间if(x==y){//如果已经到达ans=min(ans,sum);//更新时间return;}if(x>y){//如果农夫在牛右边，向左走d(x,y+1,sum+1);}else{//如果农夫在牛左边if(y%2!=0){//如果牛的位置是奇数d(x,y+1,sum+1);//牛位置+1d(x,y-1,sum+1);//牛位置-1}else{//如果牛的位置是偶数d(x,y/2,sum+1);//牛位置/2}}return;
}
int main(){cin>>n>>k;if(n>k){//如果农夫在牛右边，向左走cout<<n-k;return 0;}ans=k-n;//初始化答案为直接走到的时间d(n,k,0);//调用cout<<ans;return 0;
}