算法实验三 Problem A加1乘2平方

Problem A

加1乘2平方

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：
给定两个正整数m、n，问只能做加1、乘2和平方这三种变化，从m变化到n最少需要几次

输入：

输入两个10000以内的正整数m和n，且m小于n

输出：

输出从m变化到n的最少次数

输入样例：

1 16

输出样例：

3

#include 
#include 
using namespace std;struct rec {int num;int step;bool useful;
};
rec st, ed;
queue q;int m, n;//给定两个正整数m、n，问只能做加1、乘2和平方这三种变化，从m变化到n最少需要几次
int visited[10000][100];
int ans = 0x3f3f3f3f;
rec moveto(rec now, int i) {rec next;if (i == 0) {next.num = now.num + 1;next.step = now.step + 1;} else if (i == 1) {next.num = now.num * 2;next.step = now.step + 1;} else if (i == 2) {next.num = now.num * now.num;next.step = now.step + 1;}if (next.num > ed.num) {next.useful = false;return next;}next.useful = true;return next;
}void bfs() {q.push(st);while (q.size()) {rec now = q.front();q.pop();if (now.num == ed.num) {ans = min(ans, now.step);}for (int i = 0; i < 3; i++) { //i=0表示+1, i=1表示乘2,i=2表示平方rec next = moveto(now, i);if (next.useful == true && !visited[next.num][next.step]) {visited[next.num][next.step] = 1;q.push(next);}}}
}int main() {cin >> m >> n;st.num = m, st.step = 0;ed.num = n;bfs();if (ans != 0x3f3f3f3f) {cout << ans << endl;} else {cout << -1 << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！