2013年9月19日 星期四

2013/9/19 HSNU OJ 305 - 買醬油VI 之 四則運算問題

/* http://hoj.twbbs.org/judge/problem/view/305 */
#include <iostream>
#include <cstdio>
#include <queue>
#define INF -1

using namespace std;

int in_queue[1000001]; queue<int> que; int d[1000001];

int main()
{
    for(int i = 0; i <= 1000000; i++)
        d[i] = INF;

    int a,  b;
    scanf("%d %d", &a, &b);

    d[a] = 0; in_queue[a] = 1;
    que.push(a);

    while( !que.empty() )
    {
        int t = que.front(); int p;

        p = t+1;
        if( 0 <= p && p <= 1000000 && ( d[p]==INF || d[p] > d[t]+2 ) )
        {
            d[p] = d[t]+2;
            if( !in_queue[p]  ){ in_queue[p] = 1; que.push(p); }
        }

        p = t+2;
        if( 0 <= p && p <= 1000000 && ( d[p]==INF || d[p] > d[t]+3 ) )
        {
            d[p] = d[t]+3;
            if( !in_queue[p]  ){ in_queue[p] = 1; que.push(p); }
        }

        p = t-1;
        if( 0 <= p && p <= 1000000 && ( d[p]==INF || d[p] > d[t]+2 ) )
        {
            d[p] = d[t]+2;
            if( !in_queue[p]  ){ in_queue[p] = 1; que.push(p); }
        }

        p = t-2;
        if( 0 <= p && p <= 1000000 && ( d[p]==INF || d[p] > d[t]+3 ) )
        {
            d[p] = d[t]+3;
            if( !in_queue[p]  ){ in_queue[p] = 1; que.push(p); }
        }

        p = t*2;
        if( 0 <= p && p <= 1000000 && ( d[p]==INF || d[p] > d[t]+3 ) )
        {
            d[p] = d[t]+3;
            if( !in_queue[p]  ){ in_queue[p] = 1; que.push(p); }
        }

        p = t/2;
        if( 0 <= p && p <= 1000000 && ( d[p]==INF || d[p] > d[t]+3 ) )
        {
            d[p] = d[t]+3;
            if( !in_queue[p]  ){ in_queue[p] = 1; que.push(p); }
        }
        que.pop(); in_queue[t] = 0;
    }
    printf("%d\n", d[b]);
}

沒有留言:

張貼留言