AcWing 1100. 抓住那头牛

题目传送门

#include 
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, k;
int q[N];
int dist[N];
int Min = INF;
void bfs() {
    //初始化距离数组-1
    memset(dist, -1, sizeof dist);

    int hh = 0, tt = -1;
    q[++tt] = n; //加入起点n
    dist[n] = 0; // n距离出发点0个长度

    while (hh <= tt) {
        int t = q[hh++];
        if (t == k) {
            Min = dist[k];
            return;
        }
        if (t + 1 < N && dist[t + 1] == -1) {
            dist[t + 1] = dist[t] + 1;
            q[++tt] = t + 1;
        }
        if (t - 1 >= 0 && dist[t - 1] == -1) {
            dist[t - 1] = dist[t] + 1;
            q[++tt] = t - 1;
        }
        if (t * 2 < N && dist[t * 2] == -1) {
            dist[t * 2] = dist[t] + 1;
            q[++tt] = t * 2;
        }
    }
}

int main() {
    //农夫起始位于点N，牛位于点K
    cin >> n >> k;
    bfs();
    cout << Min << endl;
    return 0;
}