每日一练（简单）！？

Question

描述

2022是小东发明的一个猜数字的游戏, 每次由小东说一个数字, 你可以对这个数字作如下变化

1.对这个数字+1

2.对这个数字-1

3.让这个数字X2

经过多次变化之后, 数字就可以变成2022

请你告诉小东, 这个数字最少需要几次可以变成2022呢 ?

输入
每组数据只有一个整数 N ( 1 <= N<= 2022 ).

输出
请输出 N 变为2022的最少次数.

输入样例 1

2022
输出样例 1

0
输入样例 2

1011
输出样例 2

1
输入样例 3

2021
输出样例 3

1

Answer 1

#include <iostream>
#include <queue>
#include <set>
using namespace std;
struct State {
    int num;
    int steps;
};

int minTo2022(int n) {
    queue<State> q;
    set<int> visited;

    q.push({n, 0});
    visited.insert(n);

    while (!q.empty()) {
        State curr = q.front();
        q.pop();
        if (curr.num == 2022) {
            return curr.steps;
        }

        // 加1
        int nextNum = curr.num + 1;
        if (visited.find(nextNum) == visited.end()) {
            q.push({nextNum, curr.steps + 1});
            visited.insert(nextNum);
        }

        // 减1
        nextNum = curr.num - 1;
        if (visited.find(nextNum) == visited.end()) {
            q.push({nextNum, curr.steps + 1});
            visited.insert(nextNum);
        }

        // 乘2
        nextNum = curr.num * 2;
        if (visited.find(nextNum) == visited.end()) {
            q.push({nextNum, curr.steps + 1});
            visited.insert(nextNum);
        }
    }

    return -1; // 如果无法得到结果，则返回-1
}

int main() {
    int num;
    cin >> num;
    cout << minTo2022(num) << endl;
    return 0;
}