抓住那头牛

搜索最短路 BFS

题目

信息学奥赛一本通（C++版）在线评测系统 农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N$(0\le N\le 100000)$，牛位于点$K(0\le K\le 100000)$。农夫有两种移动方式：

1、从$X$移动到$X-1$或$X+1$，每次移动花费一分钟

2、从$X$移动到$2\times X$，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

输入格式

两个整数，$N$和$K$。

输出格式

一个整数，农夫抓到牛所要花费的最小分钟数。

样例

输入

5 17

输出

4

思路

抽象点的走迷宫, 对于任意一点, 枚举能走的方向所对应的位置, 判断是否走过即可。 这里的队列最大值可以设定为2e5, 即每次只走+1, 最多也就往队列加两倍的元素。

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6;
int n, k;
int q[N];
int dist[N];
int hh = 0, tt = 0;
 
void slove(int i, int t)
{
    if (i > 0 && i <= 100000 && dist[i] == -1)
        q[++tt] = i, dist[i] = dist[t] + 1;
}
 
void bfs()
{
    q[0] = n;
    memset(dist, -1, sizeof dist);
    dist[n] = 0;
    while (hh <= tt)
    {
        int t = q[hh++];
        if (t == k)
            return;
        slove(t - 1, t);
        slove(t + 1, t);
        slove(t * 2, t);
    }
}
 
int main()
{
    cin >> n >> k;
    bfs();
    cout << dist[k] << endl;
    return 0;
}