HDU 2717 Catch That Cow(bfs)
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,0
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.
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef struct{
int p;
int step;
}node;
int book[100005];
queue<node> q;
int n, k;
int main()
{
scanf("%d%d", &n, &k);
if (n==k){
printf("0");
return 0;
}
while (!q.empty())
q.pop();
node t;
t.p=n;
t.step=0;
book[n]=1;
q.push(t);
while (!q.empty()){
node tmp=q.front();
q.pop();
int tx=tmp.p-1;
if (tx>=0 && tx<=100000 && book[tx]==0){
book[tx]=1;
t.p=tx;
t.step=tmp.step+1;
q.push(t);
if (t.p==k){
printf("%d", t.step);
return 0;
}
}
tx=tmp.p+1;
if (tx>=0 && tx<=100000 && book[tx]==0){
book[tx]=1;
t.p=tx;
t.step=tmp.step+1;
q.push(t);
if (t.p==k){
printf("%d", t.step);
return 0;
}
}
tx=tmp.p*2;
if (tx>=0 && tx<=100000 && book[tx]==0){
book[tx]=1;
t.p=tx;
t.step=tmp.step+1;
q.push(t);
if (t.p==k){
printf("%d", t.step);
return 0;
}
}
}
return 0;
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)