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 minuteTeleporting: 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.这是一道一维空间上的bfs,比较简单,但多数情况是在二维甚至三维空间上bfs.此时需要用结构体保存不同坐标轴上的位置.
/************************************************************************* > File Name: poj3278.cpp > Author:ukiy > Mail: > Created Time: 2016年12月03日 星期六 19时03分45秒 ************************************************************************/ #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<string> #include<cstring> #include<vector> #include<set> #include<list> #include<map> #include<queue> int dire[4][2]={ {0,1},{1,0},{0,-1},{-1,0} }; int dire2[8][2]={{-1,-1},{-1,0},{-1,1},{ 0,-1},{ 0,1},{ 1,-1},{ 1,0},{ 1,1}}; #define rep(i,a,b) for(int i=(a);i<=(b);(i++)) #define inf 0x3f3f3f #define ll long long #define pi acos(-1) int dire3[6][3]={ {0,0,1},{0,1,0},{1,0,0},{0,0,-1},{0,-1,0},{-1,0,0} }; using namespace std; const int maxn=100001; int visit[maxn+10]; int step[maxn+10]; queue<int> q; int n,k; int main() { std::ios::sync_with_stdio(false); #ifndef OnlineJudge //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); #endif cin>>n>>k; memset(visit,0,sizeof(visit)); q.push(n); step[n]=0; visit[n]=1; while(!q.empty()){ int head,next; head=q.front(); q.pop(); rep(i,0,2){ if(i==0) next=head-1; if(i==1) next=head+1; if(i==2) next=head*2; if(next>=0 &&next<=maxn &&!visit[next]){ q.push(next); step[next]=step[head]+1; visit[next]=1; } if(next==k){ printf("%d\n",step[next]); return 0; } } } return 0; }