欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

抓住那头牛「题解」

程序员文章站 2022-06-12 09:21:47
...

一、题目描述

农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点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;
}
相关标签: 搜索