题目:Catch That Cow(C语言实现)

n 题目描述:给定一个 n,k (0 <= n ,k <= 100,000) ;对 n 有三种操作,分别为 n=n+1,n=n-1,n=2*n 。现在要求用最少的操作次数使得 n 变为 k 。 n 样例输入:

   5 17

n 样例输出:

   4

Hint:5-10-9-18-17

代码实现:

#include<stdio.h>
#include<stdlib.h>
#include <mem.h>
#define position 100005
int n,k;
int rear=0,front=0;//rear头,front尾 
struct num{
    int x;//位置坐标
    int step;    //不数 
};
typedef struct num Node;

bool visit[position];//有没有走过的标识
 
void bfs(){
    Node steps[position]; //定义队列数组 
    
    Node start,now,next; //定义变量 
    
    memset(visit,false,sizeof(visit));//数组都没走过赋false 
    
    start.x=n;//农夫位置 
    
    start.step=0;//步数 
    
    steps[rear++]=start;//把第一个存进去 
    
    visit[start.x]=true;    
    
    while(rear!=front){//头不等于尾 
        
        now=steps[front++];//取队列首元素表示当前位置并且首元素出列
        
        if(now.x==k)//看看是否满足条件  打印结束 
        {
            printf("%d\n",now.step);
            return ;
        }
        
        for(int i=0;i<3;i++)
        {
            if(i==0)//第一种 
                next.x=now.x+1;
            if(i==1)//第二种 
                next.x=now.x-1;
            if(i==2)//第三种 
                next.x=now.x*2;
            if(next.x>=0&&next.x<position&&!visit[next.x])//肯定要大于0,同时要小于数组最大position并且不能去去过的地方 
            {
                visit[next.x]=true; //走过的位置赋true
                next.step=now.step+1; //步数加一 
                steps[rear++]=next; //入对 
            }
        }        
    } 
}
int main()
{
    scanf("%d %d",&n,&k);
    bfs();
    return 0;
}

希望大家多多评论一下

 

上一篇:mvc控制器文件上传


下一篇:阿里云内存数据库Memcache升级