暑假集训(1)第二弹 -----Catch the cow（Poj3278)

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

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.

问题分析：

简单bfs可以解答，分支为step+1；step-1；以及step*2. 第一次使用bfs以及容器；据说用容器比较慢，有时间想一想替代的方法0.0

 #include "iostream"

 #include "queue"

 using namespace std;

 char a[];

 void mset()

 {

     for (int i=;i<;i++)

          a[i] = '';

 }

 struct far

 {

     int w;

     int step;

 };

 int bfs(int n,int k)

 {

    if (n>=k)

         return n-k;

     queue<far> q;

     far fir,sec;

     fir.w = n;

     fir.step =;

     a[n] = '';

     q.push(fir);

     while (!(q.empty()))

     {

        sec=q.front();

        q.pop();

        for (int i=;i<=;i++)

        {

              switch (i)

               {

                 case  : fir.w=sec.w+; break;

                 case  : fir.w=sec.w-; break;

                 case  : fir.w=sec.w*; break;

               }

               fir.step=sec.step+;

               if (fir.w == k)   return fir.step;

               if (fir.w>= && fir.w<= && a[fir.w] == '' )

              {

                 a[fir.w] ='';

                 q.push(fir);

              }

        }

     }

 }

 int main()

 {

    int n,k;

    while (cin>>n>>k)

    {

        mset();

        cout<<bfs(n,k)<<endl;

    }

     return ;

 }

巴特西

暑假集训(1)第二弹 -----Catch the cow（Poj3278)

最新文章

热门文章