Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
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.
思路：用bfs来找最优解，注意边界问题（我错了好多次）。。。。c+1和c*2他不可能比100000大太多，不然要减很多次就不是最优解，所以c+2和c*2我都让他小于100100.
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #define Maxn 200100 using namespace std; int vis[Maxn],n,k,sum; int bfs(int a,int b) { int c; memset(vis,0,sizeof(vis)); queue<int> q; q.push(a); while(!q.empty()) { c=q.front(); q.pop(); if(c==b) { break; } if(vis[c-1]==0&&c-1>=0) { vis[c-1]=vis[c]+1; q.push(c-1); } if(vis[c+1]==0&&c+1<=Maxn/2) { vis[c+1]=vis[c]+1; q.push(c+1); } if(vis[c*2]==0&&2*c<=Maxn/2) { vis[c*2]=vis[c]+1; q.push(c*2); } } return vis[b]; } int main() { #ifdef CDZSC_OFFLINE freopen("in.txt","r",stdin); #endif while(scanf("%d%d",&n,&k)!=EOF) { if(n>=k) { printf("%d ",n-k); } else { printf("%d ",bfs(n,k)); } } return 0; }