链接：https://ac.nowcoder.com/acm/contest/6218/B 来源：牛客网
题目描述
题意：
一天，牛妹找牛牛做一个游戏，牛妹给牛牛写了一个数字n，然后又给自己写了一个数字m，她希望牛牛能执行最少的操作将他的数字转化成自己的。
操作共有三种，如下：
1.在当前数字的基础上加一，如：4转化为5
2.在当前数字的基础上减一，如：4转化为3
3.将当前数字变成它的平方，如：4转化为16
你能帮牛牛解决这个问题吗?
输入：
给定n,m,分别表示牛牛和牛妹的数字。
输出：
返回最少需要的操作数。
示例1
输入
3,10
代码语言：javascript复制3,10输出
2
代码语言：javascript复制2备注:
代码语言：javascript复制(1≤n,m≤1000)(1leq n,mleq1000)(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 ;
}
};这道题我没有做上来 但是看了大家AC的代码都是使用队列 看来就是要使用这个方法 但是我不太会 哈
队列每次操作的 次数会越来越多 so~
队列这个思想 就算操作次数 的确 懂了哈哈
