Author: lllyouo
Date: 20250812
tag: 简单搜索
link: https://www.luogu.com.cn/problem/P1588

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int d[N];

void bfs(int x, int y) {
    memset(d, -1, sizeof d);
    d[x] = 0;
    queue<int> q;
    q.push(x);

    while (q.size()) {
        int x = q.front();
        q.pop();

        if (x == y) break;

        if (x + 1 > 0 && x + 1 < N && d[x + 1] == -1) {
            d[x + 1] = d[x] + 1;
            q.push(x + 1);
        }
        if (x - 1 > 0 && d[x - 1] == -1) {
            d[x - 1] = d[x] + 1;
            q.push(x - 1);
        }
        if (2 * x > 0 && 2 * x < N && d[2 * x] == -1) {
            d[2 * x] = d[x] + 1;
            q.push(2 * x);
        }
    }
    cout << d[y] << endl;
}

int main() {
    int T; cin >> T;
    while (T--) {
        int x, y; cin >> x >> y;

        bfs(x, y);
    }

    return 0;
}