变幻莫测

[题目链接](https://www.nowcoder.com/practice/a704b3aa55ce48dfaf854bf7c7b3c989)

思路

题意是：给两个整数 $a$ 和 $b$ ，每次可以做两种操作中的一种：

操作一（交换）：把 $(a, b)$ 变成 $(b, a)$ 。
操作二（变换）：把 $(a, b)$ 变成 $(a+b,\; a-b)$ 。

问最少操作几次能让 $a = b$ ，做不到就输出 $-1$ 。

先观察操作二的性质。做一次操作二后，新的一对数的和是 $(a+b)+(a-b) = 2a$ ，差是 $(a+b)-(a-b) = 2b$ 。如果连续做两次操作二， $(a, b) \to (a+b, a-b) \to (2a, 2b)$ ，相当于同时乘以 2。这说明操作二会让数值快速增长，不可能无限做下去，搜索空间是有限的。

什么时候 $a = b$ ？做完操作二后 $a+b = a-b$ 意味着 $b = 0$ 。所以关键是：能不能通过若干步操作把 $b$ （或交换后的 $a$ ）变成 0？

由于数据范围很小（ $|a|, |b| \le 100$ ），而且操作二会让数值指数级增长，所以从起始状态出发，BFS 搜索所有可达状态即可。每个状态是一个 $(a, b)$ 二元组，每步有两种转移。数值增长很快，几十步内要么找到答案，要么数值爆炸，因此加一个合理的边界限制就行。

具体做法：

把 $(a, b)$ 作为初始状态放入队列。
每次取出队首，分别尝试两种操作生成新状态。
如果新状态满足两个分量相等，返回当前步数 $+1$ 。
对操作二生成的状态，限制绝对值不超过一个阈值（比如 $10^5$ ），避免无意义地膨胀。
用哈希表记录已访问状态，防止重复。
搜索结束仍未找到则输出 $-1$ 。

拿样例验证一下： $(5, -5) \xrightarrow{\text{op2}} (0, 10) \xrightarrow{\text{swap}} (10, 0) \xrightarrow{\text{op2}} (10, 10)$ ，三步搞定。而 $(5, 8)$ 怎么变都无法让两数相等，输出 $-1$ 。

代码

C++
Java
Python3
JavaScript

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

int main() {
    int x, y;
    cin >> x >> y;
    if (x == y) {
        cout << 0 << endl;
        return 0;
    }
    map<pair<int,int>, int> dist;
    queue<pair<int,int>> q;
    dist[{x, y}] = 0;
    q.push({x, y});
    while (!q.empty()) {
        auto [a, b] = q.front();
        q.pop();
        int d = dist[{a, b}];
        if (d > 40) break;
        // 操作一：交换
        pair<int,int> s1 = {b, a};
        if (s1.first == s1.second) {
            cout << d + 1 << endl;
            return 0;
        }
        if (!dist.count(s1)) {
            dist[s1] = d + 1;
            q.push(s1);
        }
        // 操作二：(a+b, a-b)
        pair<int,int> s2 = {a + b, a - b};
        if (s2.first == s2.second) {
            cout << d + 1 << endl;
            return 0;
        }
        if (abs(s2.first) <= 100000 && abs(s2.second) <= 100000 && !dist.count(s2)) {
            dist[s2] = d + 1;
            q.push(s2);
        }
    }
    cout << -1 << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt(), y = sc.nextInt();
        if (x == y) {
            System.out.println(0);
            return;
        }
        Map<Long, Integer> dist = new HashMap<>();
        Queue<int[]> q = new LinkedList<>();
        dist.put(encode(x, y), 0);
        q.add(new int[]{x, y});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int a = cur[0], b = cur[1];
            int d = dist.get(encode(a, b));
            if (d > 40) break;
            // 操作一：交换
            if (b == a) { System.out.println(d); return; }
            long k1 = encode(b, a);
            if (b == a) { System.out.println(d + 1); return; }
            if (!dist.containsKey(k1)) {
                dist.put(k1, d + 1);
                q.add(new int[]{b, a});
            }
            // 操作二：(a+b, a-b)
            int na = a + b, nb = a - b;
            if (na == nb) { System.out.println(d + 1); return; }
            if (Math.abs(na) <= 100000 && Math.abs(nb) <= 100000) {
                long k2 = encode(na, nb);
                if (!dist.containsKey(k2)) {
                    dist.put(k2, d + 1);
                    q.add(new int[]{na, nb});
                }
            }
        }
        System.out.println(-1);
    }

    static long encode(int a, int b) {
        return (long)(a + 200000) * 400001 + (b + 200000);
    }
}

from collections import deque

def solve():
    x, y = map(int, input().split())
    if x == y:
        print(0)
        return
    dist = {(x, y): 0}
    q = deque([(x, y)])
    while q:
        a, b = q.popleft()
        d = dist[(a, b)]
        if d > 40:
            break
        # 操作一：交换
        if (b, a) not in dist:
            if b == a:
                print(d + 1)
                return
            dist[(b, a)] = d + 1
            q.append((b, a))
        # 操作二：(a+b, a-b)
        na, nb = a + b, a - b
        if na == nb:
            print(d + 1)
            return
        if abs(na) <= 100000 and abs(nb) <= 100000 and (na, nb) not in dist:
            dist[(na, nb)] = d + 1
            q.append((na, nb))
    print(-1)

solve()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const [x, y] = line.trim().split(' ').map(Number);
    if (x === y) {
        console.log(0);
        process.exit();
    }
    const dist = new Map();
    const q = [[x, y]];
    const key = (a, b) => a * 400001 + b;
    dist.set(key(x, y), 0);
    let head = 0;
    while (head < q.length) {
        const [a, b] = q[head++];
        const d = dist.get(key(a, b));
        if (d > 40) break;
        // 操作一：交换
        const k1 = key(b, a);
        if (b === a) { console.log(d + 1); process.exit(); }
        if (!dist.has(k1)) {
            dist.set(k1, d + 1);
            q.push([b, a]);
        }
        // 操作二：(a+b, a-b)
        const na = a + b, nb = a - b;
        if (na === nb) { console.log(d + 1); process.exit(); }
        if (Math.abs(na) <= 100000 && Math.abs(nb) <= 100000) {
            const k2 = key(na, nb);
            if (!dist.has(k2)) {
                dist.set(k2, d + 1);
                q.push([na, nb]);
            }
        }
    }
    console.log(-1);
    process.exit();
});

复杂度分析

时间复杂度：由于操作二会让数值指数级增长，可达状态数是有限的（在边界限制下为常数级别），BFS 的时间复杂度为 $O(S)$ ，其中 $S$ 是可达状态数，实际非常小。
空间复杂度： $O(S)$ ，用于存储已访问状态的哈希表和队列。