POJ Catch That Cow

----------------------- Solution: Version 1 ------------------------------------

// Accepted

#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;

#define sf scanf
#define pf printf
#define fast ios_base::sync_with_stdio(false)

typedef long long LL;
typedef map<LL, LL>mpll;

const int high = 1e5+3;
const int limit=1e5;
const int inf = (1<<31)-1;

LL visited[high], level[high];
//mpll visited, level;

void CLR()
{
    for(int i=0; i<high; i++)
    {
        visited[i]=0;
        level[i]=0;
    }
}

void BFS(int x, int K)
{
    queue<LL>Q;

    LL v;

    visited[x]=1;

    level[x] = 0;

    Q.push(x);

    while(!Q.empty())
    {
        LL u = Q.front();
        Q.pop();

        //cout<<"root=" << u << "\n";

        for(int i=0; i<3; i++)
        {
            if(i==0) v=u-1;
            else if(i==1) v=u+1;
            else v=u*2;

            if(v>=0&&v<=limit&&!visited[v])
            {
                visited[v]=1;
                Q.push(v);
                level[v]=level[u]+1;
            }

            //cout << v << "\n";
            //cout << level[v] << "\n";
            //cout<<"----------------------\n";
        }
    }
}

int main()
{
    fast;
    int N, K;

    while(cin >> N >> K)
    {
        if(N>=K)
        {
            cout << N-K << "\n";
            continue;
        }

        CLR();

        BFS(N, K);

        cout << level[K] << "\n";
    }

    return 0;
}



------------------------- Solution: Version 2 -------------------------------

// Accepted

#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;

#define sf scanf
#define pf printf
#define fast ios_base::sync_with_stdio(false)

typedef long long LL;
typedef map<LL, LL>mpll;

const int high = 1e5+3;
const int limit=1e5;
const int inf = (1<<31)-1;

LL visited[high], level[high];
//mpll visited, level;

void CLR()
{
    for(int i=0; i<high; i++)
    {
        visited[i]=0;
        level[i]=0;
    }
}

void BFS(int x, int K)
{
    queue<LL>Q;

    LL v;

    visited[x]=1;

    level[x] = 0;

    Q.push(x);

    while(!Q.empty())
    {
        LL u = Q.front();
        Q.pop();

        //cout<<"root=" << u << "\n";

        for(int i=0; i<3; i++)
        {
            if(i==0) v=u-1;
            else if(i==1) v=u+1;
            else v=u*2;

            if(v<0||v>=high) continue;

            if(!visited[v])
            {
                visited[v]=1;
                Q.push(v);
                level[v]=level[u]+1;
            }

            if(v == K) return;

            //cout << v << "\n";
            //cout << level[v] << "\n";
            //cout<<"----------------------\n";
        }
    }
}

int main()
{
    fast;
    int N, K;

    while(cin >> N >> K)
    {
        if(N>=K)
        {
            cout << N-K << "\n";
            continue;
        }

        CLR();

        BFS(N, K);

        cout << level[K] << "\n";
    }

    return 0;
}