bfs经典问题 抓牛问题
抓住奶牛

Farmer John 已被告知一头逃亡母牛的位置，并希望立即抓住她。他从数轴上的点N (0 ≤ N ≤ 100,000) 开始，而奶牛在同一数轴上的点K (0 ≤ K ≤ 100,000) 处。Farmer John 有两种交通方式：步行和传送。

行走：FJ 可以在一分钟内从X点移动到X - 1 或X + 1点
传送：FJ 可以在一分钟内从X点移动到 2 × X点。
如果母牛不知道它的追逐，根本不动，FJ需要多长时间才能把它取回？

#include<iostream>
using namespace std;
const int N=1e7+10;
int startpos,endpos;
bool st[N];//标记是否走过该点
int step;
int q[N];
int tt,hh;
bool check(int a)
{
    if(a>=0 && a<N && !st[a])return true;
    else return false;
}
int bfs(int u)
{
    tt=0,hh=0;
    while(hh<=tt)
    {
        int len=tt-hh;
        for(int i=0;i<=len;i++)//扩展当前层
        {
            int t=q[hh++];
            if(t==endpos)return step;
            else
            {
               if(check(t+1))q[++tt]=t+1,st[t+1]=true;
               if(check(t-1))q[++tt]=t-1,st[t-1]=true;
               if(check(t*2))q[++tt]=t*2,st[t*2]=true; 
            }
        }
        step++;
    }
}
int main()
{
    cin>>startpos>>endpos;
    q[0]=startpos;
    cout<<bfs(startpos)<<endl;
    return 0;
}