Problem 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,题意大概是Farmer John要抓奶牛。
Farmer John只有一下三种移动方式:
- 向前走一步,耗时一分钟。
- 向后走一步,耗时一分钟。
向前移动到当前位置的两倍N*2,耗时一分钟。
奶牛是不会动的。
通过分析可知,当奶牛在Farmer John后面时(即n >= k),Farmer John只能一步一步往回走,此时步数step = n - k.
其他情况则通过宽搜求结果。
根据宽搜的性质,所求得的结果必然是最优解。
代码如下:
#include<cstdio>
#include<queue>
#include<cstring>
const int MAX = 100000 + 5;
int n = 0, k = 0;
int step[MAX];
bool book[MAX];
bool ok(int x)//检查是否越界
{
if (x < 0 || x > MAX - 5)
return false;
return true;
}
void check(int next, int last, std::queue<int>&q)//模拟走路的方式
{
if (ok(next) && !book[next]) {
step[next] = step[last] + 1;
q.push(next);
book[next] = true;
}
}
void BFS()
{
int last = 0, next = 0;
std::queue<int> q;
book[n] = true;
step[n] = 0;
q.push(n);
while (!q.empty()) {
last = q.front();
q.pop();
if (last == k) printf("%d\n", step[last]);
next = last - 1;
check(next, last, q);
next = last + 1;
check(next, last, q);
next = last * 2;
check(next, last, q);
}
}
int main()
{
while (scanf("%d%d", &n, &k) == 2) {
memset(book, false, sizeof book);
memset(step, 0, sizeof book);
if (k <= n) printf("%d\n", n - k);
else BFS();
}
return 0;
}
刚开始时,在ok函数中,我写成if (x < 0 || x >= MAX - 5)
结果wrong answer 了。尴尬。被边界数据阴了。。。。。所以是不需要等号的。因为测试的数据中最大刚好有个100000。