POJ 3278 Catch That Cow

题目：你要去抓一头牛，给出你所在的坐标和牛所在的坐标，移动方式有两种：要么前一步或者后一步，要么移动到现在所在坐标的两倍，两种方式都要花费一分钟，问你最小花费时间恰好到达牛所在的地方。

思路：BFS求最优解，移动有三种情况，前后，和移动两倍位置，不过注意的地方是，当牛的坐标比你小，你只能一步步往后倒退，这个需要特判。

#include<cstdio>

#include<cmath>

#include<cstring>

#include<queue>

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 1010000;

int d[maxn];

int vis[maxn*2];   //貌似数据出了点问题？C++ WA  G++就过了

int N,K;

bool can(int x){

    if(vis[x])

        return 0;

    if(x<0)

        return 0;

    if(x>maxn)  //数组不能越界

        return 0;

    return 1;

}

void bfs(int x){

    queue<int>q;

    memset(vis,0,sizeof(vis));

    memset(d,0,sizeof(d));

    d[x]=0;

    vis[x] = 1;

    q.push(x);

    while(!q.empty()){

        int u = q.front();

        q.pop();

        if(u == K){

            return ;

        }

        for(int i=0;i<3;i++){  //这里三种情况，由于情况不同，所以要分别讨论

            int v;

            if(i==0)

                v = u-1;

            else if(i==1)

                v = u+1;

            else v = u*2;

            if(can(v)){

                d[v] = d[u]+1;

                q.push(v);

                vis[v] = 1;

//              printf("%d\n",v1);

            }

        }

    }

}

int main()

{

    while(~scanf("%d%d",&N,&K)){

        if(K <= N){

            printf("%d\n",N-K); //特判牛的位置比自己坐标小

            continue;

        }

        bfs(N);

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

    }

}