题解 | #变幻莫测#

题目链接

变幻莫测

题目描述

给定两个整数 $X, Y$ ( $-100 \le X, Y \le 100$ )，你可以任意顺序多次执行以下两种操作之一：

交换: $(X, Y) \to (Y, X)$
变换: $(X, Y) \to (X + Y, X - Y)$

求使 $X = Y$ 成立所需的最少操作次数；如无法实现，输出 $-1$ 。

解题思路

这是一个典型的求解最短路径问题，最直接和简单的方法是使用广度优先搜索 (BFS)。

我们可以把每对 $(x, y)$ 看作一个状态，题目中的两种操作就是连接不同状态的路径。我们的目标是从初始状态 $(X, Y)$ 出发，找到到达任意一个满足 $x=y$ 的目标状态的最短需要多少步。

BFS 的核心思想是“逐层搜索”，这保证了我们第一次找到目标状态时，所经过的路径一定是最短的。

BFS 实现步骤:

队列: 创建一个队列，用于存放待访问的状态。每个状态包含三个信息：当前的 $x$ 值，当前的 $y$ 值，以及到达此状态所用的步数。
Visited 集合: 创建一个集合，用于记录已经访问过的状态，以防止重复搜索或陷入无限循环。
初始化: 将初始状态 $(X, Y)$ 和步数 $0$ 加入队列和 visited 集合。
循环搜索:
- 从队列头部取出一个状态 (curr_x, curr_y, steps)。
- 对该状态应用“交换”操作，得到新状态 (next_x_1, next_y_1)。
- 对该状态应用“变换”操作，得到新状态 (next_x_2, next_y_2)。
- 对于这两个新状态，分别进行检查：
  - 如果 x == y，说明已到达目标，直接返回 steps + 1。
  - 如果该状态未被访问过，并且其数值在某个合理的边界内（例如绝对值小于400，防止无限增长），则将其加入队列和 visited 集合。
结束条件: 如果队列为空，说明在所有可达范围内都无法找到解，返回 $-1$ 。

代码

c++
java
python

#include <iostream>
#include <queue>
#include <set>
#include <utility>
#include <cmath>

using namespace std;

int main() {
    long long x, y;
    cin >> x >> y;

    if (x == y) {
        cout << 0 << '\n';
        return 0;
    }

    queue<pair<pair<long long, long long>, int>> q;
    set<pair<long long, long long>> visited;
    
    q.push({{x, y}, 0});
    visited.insert({x, y});
    
    long long bound = 400; // 搜索边界

    while (!q.empty()) {
        pair<long long, long long> curr = q.front().first;
        int steps = q.front().second;
        q.pop();

        pair<long long, long long> next_states[2];
        next_states[0] = {curr.second, curr.first}; // 交换
        next_states[1] = {curr.first + curr.second, curr.first - curr.second}; // 变换

        for (const auto& next : next_states) {
            if (next.first == next.second) {
                cout << steps + 1 << '\n';
                return 0;
            }
            if (visited.find(next) == visited.end() && abs(next.first) < bound && abs(next.second) < bound) {
                visited.insert(next);
                q.push({next, steps + 1});
            }
        }
    }

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long y = sc.nextLong();

        if (x == y) {
            System.out.println(0);
            return;
        }

        Queue<State> queue = new LinkedList<>();
        Set<State> visited = new HashSet<>();

        State startState = new State(x, y, 0);
        queue.add(startState);
        visited.add(startState);

        long bound = 400; // 搜索边界

        while (!queue.isEmpty()) {
            State current = queue.poll();
            
            State[] nextStates = new State[2];
            nextStates[0] = new State(current.y, current.x, current.steps + 1); // 交换
            nextStates[1] = new State(current.x + current.y, current.x - current.y, current.steps + 1); // 变换

            for (State next : nextStates) {
                if (next.x == next.y) {
                    System.out.println(next.steps);
                    return;
                }
                if (!visited.contains(next) && Math.abs(next.x) < bound && Math.abs(next.y) < bound) {
                    visited.add(next);
                    queue.add(next);
                }
            }
        }
        System.out.println(-1);
    }
}

class State {
    long x, y;
    int steps;
    State(long x, long y, int steps) { this.x = x; this.y = y; this.steps = steps; }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        State state = (State) o;
        return x == state.x && y == state.y;
    }
    @Override
    public int hashCode() { return Objects.hash(x, y); }
}

from collections import deque
import math

x, y = map(int, input().split())

if x == y:
    print(0)
else:
    q = deque([((x, y), 0)])
    visited = {(x, y)}
    bound = 400 # 搜索边界
    found = False

    while q:
        (curr_x, curr_y), steps = q.popleft()
        
        next_states = [
            (curr_y, curr_x), # 交换
            (curr_x + curr_y, curr_x - curr_y) # 变换
        ]
        
        for next_x, next_y in next_states:
            if next_x == next_y:
                print(steps + 1)
                found = True
                break
            if (next_x, next_y) not in visited and abs(next_x) < bound and abs(next_y) < bound:
                visited.add((next_x, next_y))
                q.append(((next_x, next_y), steps + 1))
        
        if found:
            break
    
    if not found:
        print(-1)

算法及复杂度

算法：广度优先搜索 (BFS)。
时间复杂度：取决于有界状态空间的大小。设边界为 $B$ , 状态数约为 $O(B^2)$ 。在每个状态，我们执行常数次操作。因此，时间复杂度近似为 $O(B^2)$ 。
空间复杂度：主要由队列和已访问集合占用，与状态数成正比，即 $O(B^2)$ 。