Catch That Cow（一条直线上的bfs）

BFS

题面链接

• 题意

  主人的牛跑掉了(主人和牛在同一水平线上)，主人有三种移动方式（向左移1，向右移1，向右移动当前位置坐标的距离即到达为当前位置二倍坐标的位置）每次移动花一分钟，当然牛是在原地不动的，求找到牛花费的最少时间。

  只有一行输入，输入n（主人的位置），k（牛的位置）(0 ≤ n，m ≤ 100,000)

• 样例

  输入
  5 17
  输出
  4
  （路线：5-10-9-18-17）

• 代码

#include<stdio.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<queue>
using namespace std;
int vis[200010];
int n,k,i,j,ans;
struct node
{
    int x,time;
};
int bfs(int x,int y)
{
    node now,next;
    queue<node>q;
    now.x=x;
    now.time=0;
    q.push(now);
    memset(vis,0,sizeof(vis));
    vis[x]=1;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(now.x==y)
           return now.time;
        next.x=now.x+1;
        if(next.x>=0&&next.x<=max(n,k)*2&&vis[next.x]==0)
        {
            next.time=now.time+1;
            vis[next.x]=1;
            q.push(next);
        }
        next.x=now.x-1;
        if(next.x>=0&&next.x<max(n,k)*2&&vis[next.x]==0)
        {
            next.time=now.time+1;
            vis[next.x]=1;
            q.push(next);
        }
        next.x=now.x*2;
        if(next.x>=0&&next.x<max(n,k)*2&&vis[next.x]==0)
        {
            next.time=now.time+1;
            vis[next.x]=1;
            q.push(next);
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
            int num=bfs(n,k);
            printf("%d\n",num);
    }
    return 0;
}

ps:最开始当n>k时这种情况的数据过不了，所以加了特判过的，但最后才找到问题，就是n,k取max那里，之前直接写的2*k。