首页 > 搜索 > BFS搜索 > hdu 2717 Catch That Cow-BFS-[解题报告]C++
2014
02-14

hdu 2717 Catch That Cow-BFS-[解题报告]C++

Catch That Cow

问题描述 :

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?

输入:

Line 1: Two space-separated integers: N and K

输出:

Line 1: Two space-separated integers: N and K

样例输入:

5 17

样例输出:

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.

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2717

刚开始思路错了,用的DP,一直WA,后来才发现是搜索,还是简单的BFS,顿时。。。。

思路:

BFS 三个方向即可;

代码:

#include<iostream>
 #include<cstdlib>
 #include<cstdio>
 #include<cmath>
 #include<cstring>
 #include<fstream>
 #include<queue>
 #define MAX 100010
 using namespace std;
 int n,k;
 int  cur,next;
 int step[MAX];
 queue<int>q;
 void bfs()
 {
         while(!q.empty())
         {
               cur=q.front();
               q.pop();
               if(cur==k)  break;
               next=cur-1;
               if(next>=0&&step[next]==0)
               {
                       q.push(next);
                       step[next]=step[cur]+1;
               }
               next=cur+1;
               if(step[next]==0)
               {
                       q.push(next);
                       step[next]=step[cur]+1;
               }
               next=cur*2;
               if(next<=100000&&(next-k)<(k-cur)&&step[next]==0)
               {
                       q.push(next);
                       step[next]=step[cur]+1;
               }
         }
 
 }
 int main()
 {
        while(scanf("%d%d",&n,&k)!=EOF)
        {
               memset(step,0,sizeof(step));
               if(n>k)
                       cout<<(n-k)<<endl;
                else
                    {
                         while(!q.empty()) q.pop();
                         q.push(n);
                         bfs();
                         cout<<step[k]<<endl;
                    }
        }
        return 0;
 }

 

解题转自:http://www.cnblogs.com/xiaozhuyang/archive/2013/08/09/hdu2717.html


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  3. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。