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; }
|
|
希望大家多多评论一下