解题思路:利用广搜
注意事项:
参考代码:
//利用广度优先搜索
//利用广度优先搜索 #include <iostream> #include <queue> using namespace std; bool vis[100005];//n和k的取值范围是0到100000,开一个100005大的数组来标记是否访问 int n,k; bool in(int x){//判断是否在0到100000这个范围 return x>=0&&x<=100000; } struct node{//定义一个结构体,x代表所在位置,step代表走了多少步,每走一步都会消耗一分钟,最后将走了多少步返回,就是最小的步数 int x,step; node(int xx,int xstep){//一个构造方法 x=xx; step=xstep; } }; int bfs(int x){ queue<node> q;//定义一个队列,类型为node q.push(node(x,0));//先让农夫开始的位置入队,step为0 vis[x]=true;//将这一点标记为true while(!q.empty()){// node now=q.front();//取队首元素 q.pop();//队首元素出队 if(in(now.x+1)&&!vis[now.x+1]){//农夫走x+1 if(now.x+1==k){//如果农夫到了牛的位置,就返回此时的步数加一 return now.step+1; }else{//如果没有则入队 vis[now.x+1]=true; q.push(node(now.x+1,now.step+1)); } } if(in(now.x-1)&&!vis[now.x-1]){//农夫走x-1 if(now.x-1==k){ return now.step+1; }else{ vis[now.x-1]=true; q.push(node(now.x-1,now.step+1)); } } if(in(now.x*2)&&!vis[now.x*2]){//农夫走x*2 if(now.x*2==k){ return now.step+1; }else{ vis[now.x+1]=true; q.push(node(now.x*2,now.step+1)); } } } return -1;// } int main(){ scanf("%d%d",&n,&k); printf("%d",bfs(n)); return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题11.12 (C语言代码)浏览:724 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:667 |
C语言训练-立方和不等式 (C语言代码)浏览:751 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:734 |
C语言训练-排序问题<1> (C语言代码)浏览:601 |
printf基础练习2 (C语言代码)浏览:942 |
简单的a+b (C语言代码)浏览:606 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:373 |
蚂蚁感冒 (C语言代码)浏览:1333 |
字符逆序 (C语言代码)浏览:460 |