本文主要是介绍「题解」抓住那头牛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目描述
农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:
1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?
二、输入格式
两个整数,N和K
三、输出格式
一个整数,农夫抓到牛所要花费的最小分钟数
四、样例
1、样例输入
5 17
2、样例输出
4
五、分析
这道题用深搜
也不是绝对不可以的
画个图说明一下
这里仅仅只有几个数据,用广搜和深搜效果差不了太多
但如果数据较复杂一点
就会像这样
当然,用一般的广搜也是有问题的
比如这两种
所以我们可以定义一个used数组,用于储存最短路径并且排除重复的情况以及越界
同时定义一个队列(或栈)来搜索(不断弹出队首元素,并把其分支排入队尾,并将搜索结果储存到used数组中)
六、完整代码
#include <cstdio>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;const int M = 1e6 + 5;
int n, m;
int used[M];
queue<int> a;void bfs() {while(true) {int temp = a.front();a.pop();if(temp + 1 <= M && used[temp + 1] == -1) {used[temp + 1] = used[temp] + 1;a.push(temp + 1);}if(temp - 1 <= M && used[temp - 1] == -1) {used[temp - 1] = used[temp] + 1;a.push(temp - 1);}if(temp * 2 <= M && used[temp * 2] == -1) {used[temp * 2] = used[temp] + 1;a.push(temp * 2);}if(used[m] != -1) return ;}
}int main() {scanf("%d %d", &n, &m);a.push(n);memset(used, -1, sizeof used);//标记未搜索位置 used[n] = 0;bfs();printf("%d", used[m]);return 0;
}
这篇关于「题解」抓住那头牛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!