poj3278 广搜

/**

广搜，有两点剪枝

1、当人在牛右边时（i>K），只要-1

2、广搜过程不会超过边界100000

          2i超过边界的不可能是最优解
          设边界为2k，假设2i>2k,则2i-2k>=2,到达2k花费时间为2i-2k+1>=3
           而先-1再乘2，到达2k花费时间为(i-k)*2

*/

#include<stdio.h>
#include<queue>
#include<string.h>

#define MAX 150000

using namespace std;

int count[MAX];

int main()
{
    int i,N,K,min;

    queue<int> qu;
    scanf("%d %d",&N,&K);

    if(K<=N){
        printf("%d\n",N-K);
        return 0;
    }

    for(i=0;i<MAX; ++i)
    {
        count[i]=-1;
    }

    qu.push(N);
    count[N]=0;
    while(!qu.empty())
    {
        i = qu.front();
        qu.pop();
        if(i==K)break;
        if(i<K)//剪枝，当i>k时候，只有-1才能到达
        {
            /*
            * 2i超过边界的不可能是最优解
            * 设边界为2k，假设2i>2k,则2i-2k>=2,到达2k花费时间为2i-2k+1>=3
            * 而先-1再乘2，到达2k花费时间为(i-k)*2
            */
            if(i*2<MAX && count[i*2]==-1)
            {
                qu.push(i*2);
                count[i*2] = count[i]+1;
            }

            if(count[i+1]==-1)
            {
                qu.push(i+1);
                count[i+1] = count[i]+1;
            }
        }
        if(i-1>=0 && count[i-1]==-1)
        {
            qu.push(i-1);
            count[i-1] = count[i]+1;
        }
    }
    printf("%d\n",count[K]);
    return 0;
}