C - Catch That Cow（抓住那只牛）

题目描述：

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

• Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
• Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

题意：

在一条笔直的道路上，农民要捉牛，给出农民和牛的位置，牛不动，农民有三种方式可以走，例如农民在5，牛在17. 农民可以倍数级走，5*2。可以向前走一步5+1， 向后走一步5-1，每一种方式都花费一分钟，问最少花费的时间可以捉到牛。
分析：这是一个bfs题。用队列容器可以很好解决，也可以用数组模拟队列解决。我是用模拟解决的。
例如：农民在5，那么把5加入数组，那么三种走法能走到的地方分别是，6，4，10。将这三个数加入数组。
数组元素此时是：
5 6 4 10
然后i++，i变成了1。就又将a[i]也就是6能做到的三种情况即5，7，12加入队列。依次这样直到出现17，就停止。

#include"stdio.h"
#include"string.h"
typedef struct
{
    int digit;
    int step;
} Crow;
Crow crow[1000000];
int digit[100001];
int N,K;
int check(int num)
{
   if(digit[num]==0)
   {
       digit[num]=1;
       return 1;
   }
   return 0;
}
int bfs()
{
    int i=0,j=1;
    while(crow[i].digit!=K)
    {//必须加上<=100000否则会运行错误。
     //运行错误原因：数组装不下了。加上<=100000就不会出现这种情况
        if(crow[i].digit+1<=100000&&check(crow[i].digit+1))
        {
            crow[j].digit=crow[i].digit+1;
            crow[j++].step=crow[i].step+1;
        }
        if(crow[i].digit-1>=0&&check(crow[i].digit-1))
        {
            crow[j].digit=crow[i].digit-1;
            crow[j++].step=crow[i].step+1;
        }
        if(crow[i].digit*2<=100000&&check(crow[i].digit*2))
        {
            crow[j].digit=crow[i].digit*2;
            crow[j++].step=crow[i].step+1;
        }
        i++;
    }
    return i;
}
int main()
{
    while(~scanf("%d%d",&N,&K))
    {
        if(N>=K)
        {
            printf("%d\n",N-K);
        }
        else

        {
            memset(digit,0,sizeof(digit));
            crow[0].digit=N;
            crow[0].step=0;
            int i=bfs();
            printf("%d\n",crow[i].step);
        }
    }
}```