学步园

bfs

#include <iostream>
#include <queue>
const int N = 100010;
 
using namespace std;
 
queue<int> q;
bool vis[N];
int step[N];
 
int bfs(int n, int k)
{
    q.push(n);
    vis[n] = true;
    step[n] = 0;
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < 3; i++)
        {
            int next;
            if (i == 0) 
                next = now - 1;
            else if (i == 1) 
                next = now + 1;
            else 
                next = now * 2;
            if (next > N || next < 0)
                continue;
            if (!vis[next])
            {
                q.push(next);
                step[next] = step[now] + 1;
                vis[next] = true;
            }
            if (next == k) 
                return step[next];
        }
    }
    return -1;
}
 
int main()
{
    int n, k;
    while( cin >> n >> k )
    {
        if (n >= k)
            cout << n - k << endl;
        else
        {
            if( bfs( n, k ) )
                cout << bfs(n, k) << endl;
        }
    }
    return 0;
}