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
Output
Sample Input
5 17
Sample Output
4
Hint
Source
#include<cstdio> #include<cstring> #include<queue> using namespace std; int n,p,countn,k; struct edge{ int x; int c; }a[200010]; queue <edge> q; int visit[200010]; int bfs() { while(!q.empty()){ p = q.front().x; countn = q.front().c; q.pop(); if(p == k) return countn; if(!visit[p-1] && p > 0){ visit[p-1] = 1; a[p-1].x = p-1; a[p-1].c = countn+1; q.push(a[p-1]); } if(p < k){ if(!visit[p+1]){ visit[p+1] = 1; a[p+1].x = p+1; a[p+1].c = countn+1; q.push(a[p+1]); } if(!visit[p*2]){ visit[p*2] = 1; a[p*2].x = p*2; a[p*2].c = countn+1; q.push(a[p*2]); } } } } int main() { while(~scanf("%d%d",&n,&k)){ memset(visit,0,sizeof(visit)); memset(a,0,sizeof(a)); while(!q.empty()) q.pop(); visit[n] = 1; a[n].x = n; a[n].c = 0; q.push(a[n]); printf("%d\n",bfs()); } return 0; }
原文：http://www.cnblogs.com/zero-begin/p/4340104.html
