3048: 抓住那头牛

解题思路:广度优先算法，使用队列的结构

注意事项:注意更新状态数组v[MAX_POS+1]

参考代码:

#include<stdio.h>

#include<string.h>

#define QUEUE_SIZE 200000

#define MAX_POS 100000

typedef struct{

    int pos,t;

}QueueNode;

QueueNode queue[QUEUE_SIZE];

int front=0;

int rear=0;

int v[MAX_POS+1];

void enqueue(int pos,int t){

    if(rear<QUEUE_SIZE){

        queue[rear].pos=pos;

        queue[rear].t=t;

        rear++;

    }

}

QueueNode dequeue(){

    return queue[front++];

}

int bfs(int start,int target){

    front=0;

    rear=0;

    memset(v,0,sizeof(v));

    enqueue(start,0);

    v[start]=1;

    while(front<rear){

        QueueNode cur=dequeue();

        int cur_pos=cur.pos;

        int cur_t=cur.t;

        if(cur_pos==target){

            return cur_t;

        }

        if(cur_pos-1>=0 && !v[cur_pos-1]){

            v[cur_pos-1]=1;

            enqueue(cur_pos-1,cur_t+1);

        }

        if(cur_pos+1<=MAX_POS && !v[cur_pos+1]){

            v[cur_pos+1]=1;

            enqueue(cur_pos+1,cur_t+1);

        }

        if(cur_pos*2<=MAX_POS && !v[cur_pos*2]){

            v[cur_pos*2]=1;

            enqueue(cur_pos*2,cur_t+1);

        }

    }

    return -1;

}

int main()

{

    long long N,K;

    scanf("%lld %lld",&N,&K);

    if(N>K){

        printf("%lld",N-K);

        return 0;

    }

    int min_t=bfs(N,K);

    printf("%d",min_t);

return 0;

}