Catch That Cow
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)
Total Submission(s) : 48 Accepted Submission(s) : 16
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
Source
PKU
这道题是到BFS水题，不过我在这道题上re了很多次。。。原因是我没有剪枝。
#include<iostream>
#include<cstring>
using namespace std;
int que[1000001]; //数组要开大谢；大数组用全局变量开，不能再函数里开。
int step[1000001]={0};
bool f[1000001]={false};
int n,k;
int BFS()
{
int front=0,rear=1;
que[0]=n;
step[0]=0;
f[n]=true;
if(que[front]==k)
return step[front];
while(front<rear)
{
if(que[front]<k&&!f[que[front]+1]) //只有当前的数比k小时，加一才能更接近k。
{
que[rear]=que[front]+1;
step[rear]=step[front]+1;
f[que[rear]]=true;
if(que[rear]==k)
return step[rear];
rear++;
}
if(que[front]-1>=0&&!f[que[front]-1]) //数组不能越界
{
que[rear]=que[front]-1;
step[rear]=step[front]+1;
f[que[rear]]=true;
if(que[rear]==k)
return step[rear];
rear++;
}
if(que[front]<k&&!f[que[front]*2]) //只有当前的数比k小时，乘2才有可能更接近k。
{
que[rear]=que[front]*2;
step[rear]=step[front]+1;
f[que[rear]]=true;
if(que[rear]==k)
return step[rear];
rear++;
}
front++;
}
}
int main()
{
while(cin>>n>>k)
{
memset(que,0,sizeof(que));
memset(step,0,sizeof(step));
memset(f,false,sizeof(f));
cout<<BFS()<<endl;
}
}