算法策略：广度优先搜索 (BFS)

鉴于我们需要求最少操作次数，且每一步操作的代价均等（权重为1），广度优先搜索 (BFS) 是最优选择。

核心逻辑

  1. 层级遍历：从初始状态出发，第一层探索 1 步可达的状态，第二层探索 2 步可达的状态，以此类推。首次遇到 的状态时，当前的层数即为最小操作次数。
  2. 状态去重：使用哈希集合（Visited Set）记录已访问过的 状态，防止因“交换”操作导致的死循环（例如：）以及重复计算。
  3. 搜索剪枝/终止条件：
    • 由于输入范围极小 ，且目标是相等。如果存在解，通常步数很少。
    • 随着变换操作， 和 会迅速呈指数级增长。如果数值超过了一定阈值（例如绝对值超过 10,000 或 100,000）仍未找到解，基于上述范数增长的性质，后续也不可能收敛到相等状态（因为数值只会越来越大且保持特定的倍数关系），此时可判定无解。

代码实现

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

struct State {
    ll x;
    ll y;
    ll steps;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int X, Y;
    cin >> X >> Y;

    if (X == Y) {
        cout << "0\n";
        return 0;
    }

    set<pair<ll, ll>> visited;

    queue<State> Q;
    const ll LIMIT = 100000;
    Q.push({X, Y, 0});

    while (!Q.empty()) {
        auto [curX, curY, curStep] = Q.front();
        Q.pop();
        if (curX == curY) {
            cout << curStep << "\n";
            return 0;
        }

        pair<ll, ll> op1 = {curY, curX};
        if (visited.find(op1) == visited.end()) {
            visited.insert(op1);
            Q.push({op1.first, op1.second, curStep + 1});
        }

        ll nextX = curX + curY;
        ll nextY = curX - curY;

        // 剪枝：检查是否超出合理数值范围
        if (abs(nextX) <= LIMIT && abs(nextY) <= LIMIT) {
            pair<ll, ll> op2 = {nextX, nextY};
            if (visited.find(op2) == visited.end()) {
                visited.insert(op2);
                Q.push({nextX, nextY, curStep + 1});
            }
        }
    }

    cout << "-1\n";
    return 0;
}

复杂度分析

1. 时间复杂度

算法的时间复杂度取决于访问的状态总数。

  • 理论上状态空间是无限的，但受限于两点：
    1. 数值增长：变换操作使范数翻倍。对于 32 位整数，约 30 次变换后溢出。对于任何实际有意义的解，步数通常很小。
    2. 边界剪枝：我们设定了一个数值上限 （例如 ）。
  • 在范围 内，尽管整数点很多，但从 出发能到达的轨迹是非常稀疏的树状结构。
  • 设搜索的最大有效深度为 （受限于数值溢出或阈值，约 20-30）。每一层状态数最多翻倍。
  • 实际上，重复状态会被 Visited 集合过滤。对于小范围输入 ，有效状态数 远小于网格总点数。
  • 时间复杂度：，其中 是到达边界 或目标之前的可达状态数。对于本题约束，这是一个很小的常数级计算量。

2. 空间复杂度

  • 空间复杂度：。
  • 需要存储 Visited 集合和 BFS 队列。空间消耗与访问的状态数量成正比。