bfs(最短路径)

http://poj.org/problem?id=3278

Catch That Cow

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 146388		Accepted: 44997

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.

//#include <bits/stdc++.h>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <algorithm>

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdio.h>

#include <queue>

#include <stack>;

#include <map>

#include <set>

#include <string.h>

#include <vector>

#define ME(x , y) memset(x , y , sizeof(x))

#define SF(n) scanf("%d" , &n)

#define rep(i , n) for(int i = 0 ; i < n ; i ++)

#define INF  0x3f3f3f3f

#define mod 1000000007

using namespace std;

typedef long long ll ;

int vis[];

int ans[];

int n , m ;

void bfs(int b)

{

    queue<int>q;

    memset(vis ,  , sizeof(vis));

    memset(ans ,  , sizeof(ans));

    if(n < m)

    {

        q.push(b);

        vis[b] =  ;

        ans[b] =  ;

        while(!q.empty())

        {

            int x = q.front();

            if(x == m)

            {

                printf("%d\n" , ans[m]);

                break ;

            }

            q.pop() ;

            if(x >=  && x <=  && !vis[x*])

            {

                vis[*x] =  ;

                ans[*x] += vis[x] + ans[x];

                q.push(*x);

            }

            if(x >=  && !vis[x+])

            {

                vis[x+] =  ;

                ans[x+] += vis[x] + ans[x];

                q.push(x+);

            }

            if(x -  >=  && !vis[x-])

            {

                vis[x-] =  ;

                ans[x-] += vis[x] + ans[x];

                q.push(x-);

            }

        }

    }

    else

    {

        printf("%d\n" , n - m);

    }

}

int main()

{

    while(~scanf("%d%d" , &n , &m))

    {

        bfs(n);

    }

    return ;

}

巴特西

bfs(最短路径)

最新文章

热门文章