HDU2717（POJ3278）:Catch That Cow
这个题可把我坑惨了。
HDU和POJ的输入格式不一样
POJ是只输入一行
HDU是输入多行。
所以导致了在POJ AC的题到了HDU就变成了WA。。。。
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
Output
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]
哈哈大帝
2017年4月1日 下午7:23
加油
zqqian
2017年4月5日 下午11:00
谢谢你