# HDU2717（POJ3278）:Catch That Cow

HDU和POJ的输入格式不一样

POJ是只输入一行

HDU是输入多行。

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

[code lan=”c”]#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n, k;
struct localx {
int local;
int step;
}now, tnext;
int vis[1000010] = { 0 };
int bfs() {
queue<struct localx>q;
now.local = n;
now.step = 0;
q.push(now);
vis[n] = 1;
while (!q.empty()) {
now = q.front();
q.pop();
if (now.local == k) {
return now.step;
}

if (now.local >= 0 && now.local<k) {

//+1
tnext.local = now.local + 1;
tnext.step = now.step + 1;
if (!vis[tnext.local]) {
vis[tnext.local] = 1;
q.push(tnext);
}

//-1
tnext.local = now.local – 1;
tnext.step = now.step + 1;
if (!vis[tnext.local]) {
vis[tnext.local] = 1;
q.push(tnext);
}
//*2
tnext.local = now.local * 2;
tnext.step = now.step + 1;
if (!vis[tnext.local]) {
vis[tnext.local] = 1;
q.push(tnext);
}
}
if (now.local>k&&now.local <= 100000) {
tnext.local = now.local – 1;
tnext.step = now.step + 1;
q.push(tnext);
}
}

}
int main() {
//cin >> n >> k;
//int sum = bfs();
//cout << sum << endl;
while (scanf("%d%d", &n, &k)!=EOF)
{
memset(vis,0, sizeof(vis));
int sum = bfs();
printf("%d\n", sum);
}
return 0;
}[/code]

2条评论
• 哈哈大帝

2017年4月1日 下午7:23

加油

1. zqqian

2017年4月5日 下午11:00

谢谢你