「题解」抓住那头牛

「题解」抓住那头牛

一、题目描述

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