【牛客网】魔法数字

3,10

2

(1≤n,m≤1000)(1\leq n,m\leq1000)(1≤n,m≤1000)

class Solution {
public:
    /**
     * 返回最后要输出的答案
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    int solve(int n, int m) {
        queue<pair<int,int>> q ;
        int limit = int(1e8) ;
        vector<bool> vis(limit + 1 , false) ;
        vis[n] = true ;
        q.push({n , 0}) ;
        while (!q.empty()) {
            auto temp = q.front() ; q.pop() ;
            if (temp.first == m) {
                return temp.second ;
            }
            // + 1
            if (temp.first + 1 <= limit) {
                if (!vis[temp.first + 1]) {
                    vis[temp.first + 1] = true ;
                    q.push({temp.first + 1 , temp.second + 1}) ;
                }
            }
            // - 1
            if (temp.first > 1) {
                if (!vis[temp.first - 1]) {
                    vis[temp.first - 1] = true ;
                    q.push({temp.first - 1 , temp.second + 1}) ;
                }
            }
            // ^2
            if (temp.first <= limit / temp.first + 1) {
                if (!vis[temp.first * temp.first]) {
                    vis[temp.first * temp.first] = true ;
                    q.push({temp.first * temp.first , temp.second + 1}) ;
                }
            }
        }
        return 0 ;
    }
};