抓住那头牛「题解」

一、题目描述

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点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;
}