python/TangDou/Bfs/1384.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 100000, M = N + 10;
struct Node {
    int pos;
    int step;
};
bool st[M];
int main() {
    int n, k; //农夫位置，牛的位置
    cin >> n >> k;

    queue<Node> q;
    q.push({n, 0}); //农夫位置，步数
    st[n] = true;

    while (q.size()) {
        auto t = q.front();
        q.pop();
        //出口
        if (t.pos == k) {
            cout << t.step << endl;
            break;
        }
        if (t.pos + 1 <= N && !st[t.pos + 1]) {
            q.push({t.pos + 1, t.step + 1});
            st[t.pos + 1] = true;
        }
        if (t.pos - 1 >= 0 && !st[t.pos - 1]) {
            q.push({t.pos - 1, t.step + 1});
            st[t.pos - 1] = true;
        }
        if (t.pos * 2 <= N && !st[t.pos * 2]) {
            q.push({t.pos * 2, t.step + 1});
            st[t.pos * 2] = true;
        }
    }
    return 0;
}