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

﹏ヽ暗。殇╰゛Y 2022-03-20 08:00 154阅读 0赞

### 题目描述： ###

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);
            }
        }
    }```