| 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.
Source
思路：裸BFS可过
AC代码：
#include <cstdio>
#include <queue>
using namespace std;
queue <int> q;
int n, k;
int step[100010];
bool vis[100010];
void input()
{
scanf("%d%d", &n, &k);
}
inline bool check(int pos)
{
if (pos < 0 || pos > 100000 || vis[pos])
return 0;
return 1;
}
void bfs()
{
q.push(n);
while (!q.empty())
{
int u = q.front();
q.pop();
if (u == k)
{
printf("%d\n", step[u]);
return;
}
if (check(u + 1))
{
step[u + 1] = step[u] + 1;
vis[u + 1] = 1;
q.push(u + 1);
}
if (check(u - 1))
{
step[u - 1] = step[u] + 1;
vis[u - 1] = 1;
q.push(u - 1);
}
if (check(u * 2))
{
step[u * 2] = step[u] + 1;
vis[u * 2] = 1;
q.push(u * 2);
}
}
}
int main()
{
input();
bfs();
return 0;
}