python/TangDou/Bfs/1384_PII.cpp

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
const int N = 100000, M = N + 10;
bool st[M];
int main() {
    int n, k; //农夫位置，牛的位置
    cin >> n >> k;

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

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