链接：
http://poj.org/problem?id=3278
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 62113 | Accepted: 19441 |
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.
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue> using namespace std; #define N 110000 struct node
{
int x, step;
}; int s, e;
bool vis[N]; int BFS(int s)
{
node p, q;
p.x = s, p.step = ; memset(vis, false, sizeof(vis));
vis[s] = true;
queue<node>Q;
Q.push(p); while(Q.size())
{
p = Q.front(), Q.pop(); if(p.x == e) return p.step; for(int i=; i<; i++)
{
if(i==)
q.x = p.x + ;
else if(i==)
q.x = p.x - ;
else if(i==)
q.x = p.x * ; q.step = p.step + ;
if(q.x>= && q.x<N && !vis[q.x])
{
Q.push(q);
vis[q.x] = true;
}
}
} return -;
} int main()
{
while(scanf("%d%d", &s, &e)!=EOF)
{
int ans = BFS(s); printf("%d\n", ans);
}
return ;
}