题解 | 求x到y的最少计算次数

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int minOperations(int x, int y) {
        // 如果x等于y，不需要操作
        if (x == y) return 0;
        
        // 使用队列存储状态和操作次数
        queue<pair<int, int>> q;
        unordered_set<int> visited;
        
        q.push({x, 0});
        visited.insert(x);
        
        while (!q.empty()) {
            int curr = q.front().first;
            int steps = q.front().second;
            q.pop();
            
            // 尝试三种操作
            vector<int> next = {curr + 1, curr - 1, curr * 2};
            
            for (int nextNum : next) {
                // 检查是否超出范围
                if (nextNum < -1000 || nextNum > 1000) continue;
                
                // 如果找到目标值
                if (nextNum == y) return steps + 1;
                
                // 如果是新状态，加入队列
                if (visited.find(nextNum) == visited.end()) {
                    visited.insert(nextNum);
                    q.push({nextNum, steps + 1});
                }
            }
        }
        
        return -1;  // 无法达到目标值
    }
};

int main() {
    int x, y;
    scanf("%d,%d", &x, &y);
    
    Solution solution;
    printf("%d\n", solution.minOperations(x, y));
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int minOperations(int x, int y) {
            if (x == y) return 0;
            
            Queue<int[]> queue = new LinkedList<>();
            Set<Integer> visited = new HashSet<>();
            
            queue.offer(new int[]{x, 0});
            visited.add(x);
            
            while (!queue.isEmpty()) {
                int[] curr = queue.poll();
                int num = curr[0];
                int steps = curr[1];
                
                // 尝试三种操作
                int[] next = {num + 1, num - 1, num * 2};
                
                for (int nextNum : next) {
                    if (nextNum < -1000 || nextNum > 1000) continue;
                    
                    if (nextNum == y) return steps + 1;
                    
                    if (!visited.contains(nextNum)) {
                        visited.add(nextNum);
                        queue.offer(new int[]{nextNum, steps + 1});
                    }
                }
            }
            
            return -1;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(",");
        int x = Integer.parseInt(input[0]);
        int y = Integer.parseInt(input[1]);
        
        Solution solution = new Solution();
        System.out.println(solution.minOperations(x, y));
    }
}

from collections import deque

def min_operations(x: int, y: int) -> int:
    # 如果x等于y，不需要操作
    if x == y:
        return 0
        
    # 使用队列进行BFS
    queue = deque([(x, 0)])  # (数字，操作次数)
    visited = {x}
    
    while queue:
        curr, steps = queue.popleft()
        
        # 尝试三种操作
        for next_num in (curr + 1, curr - 1, curr * 2):
            # 检查是否超出范围
            if next_num < -1000 or next_num > 1000:
                continue
                
            # 如果找到目标值
            if next_num == y:
                return steps + 1
                
            # 如果是新状态，加入队列
            if next_num not in visited:
                visited.add(next_num)
                queue.append((next_num, steps + 1))
    
    return -1  # 无法达到目标值

if __name__ == "__main__":
    x, y = map(int, input().split(','))
    print(min_operations(x, y))