题解 | #变幻莫测#

题目描述

给出两个整数 $X, Y$ ，你可以任意顺序多次执行以下两个操作。求出使得 $X=Y$ 时所需的最少操作次数。如果无法实现，则输出 $-1$ 。

操作一： $X' = Y, Y' = X$
操作二： $X' = X+Y, Y' = X-Y$

解题思路

这是一个求解最少操作次数的问题，其状态由数对 $(X, Y)$ 定义。由于输入的初始值范围 $[-100, 100]$ 很小，这暗示我们可以通过图的搜索算法来解决。这是一个典型的广度优先搜索 (BFS) 应用场景。

1. 问题建模

状态（节点）: 每一个可能的数对 $(X, Y)$ 都是图中的一个节点。
操作（边）: 从一个状态 $(X, Y)$ 到另一个状态的两种变换（交换或线性变换）就是图中的有向边。
目标: 找到从初始状态 $(X_{start}, Y_{start})$ 到任意目标状态 $(Z, Z)$ 的最短路径。由于每次操作计为一步，所有边的权重都是 1。

2. BFS 算法

BFS 是求解无权图最短路径的标准算法，它能保证我们找到的第一个解就是步数最少的解。

队列: 我们需要一个队列来存放待处理的状态。队列中的每个元素应包含三个信息：(当前X, 当前Y, 到达此状态的步数)。
Visited 集合: 为了防止重复搜索和陷入死循环，我们需要一个集合来记录所有已经访问过的状态。
搜索边界: 操作二可能会使 $X, Y$ 的值变得很大或很小。我们需要设定一个合理的搜索边界，例如，将 $X$ 和 $Y$ 的值限制在 $[-200, 200]$ 的范围内。超出这个范围的状态通常不是最优路径的一部分，可以被剪枝。
算法流程:

a. 如果输入的 $X$ 和 $Y$ 初始就相等，则答案为 0。

b. 创建一个队列，将初始状态 (X, Y, 0) 入队。

c. 创建一个 visited 集合，并将 (X, Y) 加入。

d. 当队列不为空时，循环执行：

i. 出队一个状态 (curr_X, curr_Y, dist)。

ii. 计算两种可能的新状态：
- 操作一 (交换): (next_X1, next_Y1) = (curr_Y, curr_X)
- 操作二 (变换): (next_X2, next_Y2) = (curr_X + curr_Y, curr_X - curr_Y)
iii. 对每个新状态 (next_X, next_Y)：
- 检查是否到达终点: 如果 next_X == next_Y，则找到了最短路径，返回 dist + 1。
- 检查边界和是否已访问: 如果 next_X 和 next_Y 都在搜索边界内，并且 (next_X, next_Y) 不在 visited 集合中，则将其加入 visited 集合，并将 (next_X, next_Y, dist + 1) 入队。
e. 如果队列变空仍未找到解，说明在限定的搜索范围内无解，返回 -1。

代码

cpp
java
python

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

using namespace std;

const int BOUND = 200;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int x, y;
    cin >> x >> y;

    if (x == y) {
        cout << 0 << endl;
        return 0;
    }

    queue<tuple<int, int, int>> q;
    q.emplace(x, y, 0);

    set<pair<int, int>> visited;
    visited.insert({x, y});

    while (!q.empty()) {
        auto [cur_x, cur_y, dist] = q.front();
        q.pop();

        // Operation 1: Swap
        int next_x1 = cur_y;
        int next_y1 = cur_x;
        if (next_x1 == next_y1) {
            cout << dist + 1 << endl;
            return 0;
        }
        if (abs(next_x1) <= BOUND && abs(next_y1) <= BOUND && visited.find({next_x1, next_y1}) == visited.end()) {
            visited.insert({next_x1, next_y1});
            q.emplace(next_x1, next_y1, dist + 1);
        }

        // Operation 2: Transform
        int next_x2 = cur_x + cur_y;
        int next_y2 = cur_x - cur_y;
        if (next_x2 == next_y2) {
            cout << dist + 1 << endl;
            return 0;
        }
        if (abs(next_x2) <= BOUND && abs(next_y2) <= BOUND && visited.find({next_x2, next_y2}) == visited.end()) {
            visited.insert({next_x2, next_y2});
            q.emplace(next_x2, next_y2, dist + 1);
        }
    }

    cout << -1 << endl;
    return 0;
}

import java.util.*;

public class Main {
    private static final int BOUND = 200;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();

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

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y, 0});

        Set<String> visited = new HashSet<>();
        visited.add(x + "," + y);

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int curX = current[0];
            int curY = current[1];
            int dist = current[2];

            // Operation 1: Swap
            int nextX1 = curY;
            int nextY1 = curX;
            if (nextX1 == nextY1) {
                System.out.println(dist + 1);
                return;
            }
            if (Math.abs(nextX1) <= BOUND && Math.abs(nextY1) <= BOUND && !visited.contains(nextX1 + "," + nextY1)) {
                visited.add(nextX1 + "," + nextY1);
                queue.offer(new int[]{nextX1, nextY1, dist + 1});
            }

            // Operation 2: Transform
            int nextX2 = curX + curY;
            int nextY2 = curX - curY;
            if (nextX2 == nextY2) {
                System.out.println(dist + 1);
                return;
            }
            if (Math.abs(nextX2) <= BOUND && Math.abs(nextY2) <= BOUND && !visited.contains(nextX2 + "," + nextY2)) {
                visited.add(nextX2 + "," + nextY2);
                queue.offer(new int[]{nextX2, nextY2, dist + 1});
            }
        }

        System.out.println(-1);
    }
}

import sys
from collections import deque

def solve():
    try:
        x, y = map(int, sys.stdin.readline().split())
    except (IOError, ValueError):
        return

    if x == y:
        print(0)
        return
        
    BOUND = 200
    queue = deque([(x, y, 0)])
    visited = {(x, y)}

    while queue:
        cur_x, cur_y, dist = queue.popleft()

        # Operation 1: Swap
        next_x1, next_y1 = cur_y, cur_x
        if next_x1 == next_y1:
            print(dist + 1)
            return
        if abs(next_x1) <= BOUND and abs(next_y1) <= BOUND and (next_x1, next_y1) not in visited:
            visited.add((next_x1, next_y1))
            queue.append((next_x1, next_y1, dist + 1))

        # Operation 2: Transform
        next_x2, next_y2 = cur_x + cur_y, cur_x - cur_y
        if next_x2 == next_y2:
            print(dist + 1)
            return
        if abs(next_x2) <= BOUND and abs(next_y2) <= BOUND and (next_x2, next_y2) not in visited:
            visited.add((next_x2, next_y2))
            queue.append((next_x2, next_y2, dist + 1))

    print(-1)

solve()

算法及复杂度

算法：广度优先搜索 (BFS)
时间复杂度： $O(C^2)$ ，其中 $C$ 是我们设定的搜索边界大小。在最坏的情况下，我们需要访问边界内所有可能的状态。由于每个状态最多扩展出两个新状态，边数与顶点数是同阶的。
空间复杂度： $O(C^2)$ ，主要用于存储队列和 visited 集合。