Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a pointN(0 ≤N≤ 100,000) on a number line and the cow is at a pointK(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 pointXto the pointsX- 1 orX+ 1 in a single minute* Teleporting: FJ can move from any pointXto the point 2 ×Xin 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:NandK
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这题可以用宽搜，但要注意剪枝，，否则队列会爆。#include<stdio.h>#include<string.h>int n,m,x2,x1;int q[11111111],b[200005];void bfs(){int i,j,front=1,rear=1,x,xx;memset(q,0,sizeof(q));memset(b,0,sizeof(b));b[x1]=0;q[front]=x1;while(front<=rear){x=q[front];if(x==x2)break;front++;if(x+1<=100000 && b[x+1]==0){rear++;q[rear]=x+1;b[x+1]=b[x]+1;}if(2*x<=200000 && b[2*x]==0){rear++;q[rear]=2*x;b[2*x]=b[x]+1;}if(x>=1 && b[x-1]==0 ){rear++;q[rear]=x-1;b[x-1]=b[x]+1;}//}return;}int main(){int i,j;while(scanf("%d%d",&n,&m)!=EOF){x1=n;x2=m;bfs();printf("%d\n",b[x2]);}return 0;}
只要看得开放得下，何愁没有快乐的春莺在啼鸣，
