HDU2717(POJ3278):Catch That Cow

作者: qwq 分类: ACM 发布时间: 2017-03-21 23:01

这个题可把我坑惨了。

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

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]

  • 哈哈大帝

    2017年4月1日 下午7:23

    加油

    1. zqqian

      2017年4月5日 下午11:00

      谢谢你

发表评论

电子邮件地址不会被公开。 必填项已用*标注