<—点个赞吧QwQ

宣传一下算法提高课整理

农夫知道一头牛的位置，想要抓住它。

农夫和牛都位于数轴上，农夫起始位于点 $N$，牛位于点 $K$。

农夫有两种移动方式：

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

假设牛没有意识到农夫的行动，站在原地不动。

农夫最少要花多少时间才能抓住牛？

输入格式

共一行，包含两个整数N和K。

输出格式

输出一个整数，表示抓到牛所花费的最少时间。

数据范围

$0 \le N,K \le 10^5$

输入样例：

5 17

输出样例：

4

思路

这题就是一维的$BFS$，直接暴搜所有情况即可。
这里枚举的情况有限都在[0,10000]里，所以最多搜索100000次，不会TLE

代码

#include <iostream>
#include <queue>
using namespace std;
typedef pair <int,int> PII;
const int N = 100010;
int st,ed;
int vis[N];
bool check (int x) {
    return x >= 0 && x < N && !vis[x];
}
int bfs () {
    queue <PII> q;
    q.push ({st,0});
    while (!q.empty ()) {
        PII t = q.front ();
        q.pop ();
        int x = t.first,d = t.second;
        if (x == ed) return d;
        if (check (x + 1)) {
            vis[x + 1] = true;
            q.push ({x + 1,d + 1});
        }
        if (check (x - 1)) {
            vis[x - 1] = true;
            q.push ({x - 1,d + 1});
        }
        if (check (x * 2)) {
            vis[x * 2] = true;
            q.push ({x * 2,d + 1});
        }
    }
    return -1;
}
int main () {
    cin >> st >> ed;
    cout << bfs () << endl;
    return 0;
}