Catch That Cow
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 58072 | Accepted: 18061 |
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
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
广度优先搜索#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std; const int Max=1100000;
struct Point
{
int x;
int num;
};
int N,K;
bool vis[210000];
void BFS()
{
queue<Point>a;
Point s,t;
memset(vis,false,sizeof(vis));
s.num=0;
s.x=N;
a.push(s);
vis[N]=true;
while(!a.empty())
{
s=a.front();
a.pop();
if(s.x==K)
{
printf("%d\n",s.num);
return ;
}
if(!vis[s.x+1]&&s.x+1<=K*2)
{
t.x=s.x+1;
t.num=s.num+1;
a.push(t);
vis[t.x]=true;
}
if(s.x-1>=0&&!vis[s.x-1])
{
t.x=s.x-1;
t.num=s.num+1;
a.push(t);
vis[t.x]=true;
}
if(s.x*2<=K*2&&!vis[s.x*2])
{
t.x=s.x*2;
t.num=s.num+1;
a.push(t);
vis[t.x]=true;
}
} }
int main()
{ scanf("%d %d",&N,&K);
BFS();
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。