UC知道c++程序错误（ACM），跪求高手解答
来源：百度知道 编辑：UC知道 时间：2024/06/06 19:33:21
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
* 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
这题不能用动态规划做.
如果问题中, 只能前进的话, 那么你用动态规划做, 没有任何问题, 但是关键在于可以前进也可以后退, 那么你怎么划分子问题呢? 4可以由5推过来, 而5又可以由4推过来, 这个不是反复互相推吗?
所以dp是不可以的. 其实这题就是一个简单的广搜啦, 细节有些麻烦而已, 贴下代码:
#include <iostream>
#include <queue>
using namespace std;
int flag[100001] = {0};
void BFS(int N,int K)
{
int i;
queue<int> a;
a.push(N);
while(!a.empty())
{
i = a.front();
if(i == K)
{
cout<<flag[i]<<endl;
return;
}
if(i + 1 <= 100000 && flag[i + 1] == 0)
{
flag[i + 1] = flag[i] + 1;
a.push(i + 1);
}
if(i - 1 >= 0 && flag[i - 1] == 0)
{
flag[i - 1] = flag[i] + 1;
a.push(i - 1);
}
if(i * 2 <= 100000 && flag[i * 2] == 0)
{