抓住那头牛（POJ3278深搜）

题目：
农夫知道一头牛的位置，想要抓住它。农夫和牛都于数轴上 ，农夫起始位于点 N(0<=N<=100000) ，牛位于点 K(0<=K<=100000) 。
农夫有两种移动方式步行或乘车：
1、步行从 X移动到 X-1或X+1 ，每次移动花费一分钟
2、乘车从 X移动到 2*X ，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。最少要花多少时间才能抓住牛？

输入：两个整数N和K
输出：单行输出农夫抓住牛所需的最短时间（以分钟为单位）。

输入样例：
5 17
输出样例：
4

算法设计：
深度优先搜索
根据输入样例，农夫在5的位置，牛在17的位置，农夫可以先乘车到18，步行回到17，抓到牛，一共4步。

假设农夫和牛的位置分别为n和k，则求解步骤如下：
1、如果n=0，则先走一步到1，n=1，否则无法乘车，因为0的两倍还是0。
2、进行深度优先搜索，dfs（t）表示求解农夫从初始位置n到达位置t的最小步数。
如果t≤n，因为不可以向后乘车，只能一步一步地后退，则需要n-t步。
如果t为偶数，则比较从t/2位置向前乘车到t，从n一步一步向前走到t，采用哪种方式使得步数最少，取最小值。第一种方案的步数为从初始位置到达t/2的位置加上1次乘车所需步数，第二种方案的步数为t-n。
如果t为奇数，则比较t-1向前一步（步数为dfs（t-1）+1）、从t+1向后一步（步数为dfs（t+1）+1）,采用哪种方案使得步数最少，取最小值。
代码：

#include<iostream>
#include<algorithm>
using namespace std;
int n,k;

int dfs(int t){
	if(t<=n)
		return n-t;
	if(t%2)
		return min(dfs(t+1)+1,dfs(t-1)+1);
	else
		return min(dfs(t/2)+1,t-n);
}

int main(){
	while(cin>>n>>k){
		int ans=0;
		if(n==0){//特殊情况判断，很重要
			n=1;
			ans=1;
		}
		ans+=dfs(k);
		cout<<ans<<endl;
	}
	return 0;
}