joshua分享:用队列实现,相当于是BFS搜索,只有三条分支路。
求x到y的最少计算次数
http://www.nowcoder.com/questionTerminal/45d04d4d047c48768543eeec95798ed6
// 遍历该层的三个节点,分别为+1, -1, *2 // 加入待选节点前,先进行判断是否合法
#include <bits/stdc++.h> using namespace std; int main(void) { int level = -1, size = 0; int a, b; queue<int> q; // 这个地方为啥用cin输入就不对了?卡了我一个晚上啊! scanf("%d,%d", &a, &b); q.push(a); while(!q.empty()) { size = q.size(); level++; // 遍历该层的三个节点,分别为+1, -1, *2 // 加入待选节点前,先进行判断是否合法 for(int i = 0; i < size; i++) { int t = q.front(); q.pop(); // 满足要求即可退出 if(t == b) { while(!q.empty()) q.pop(); break; } // 三种待选方案 if(t+1 <= 100) q.push(t+1); if(t-1 >= -100) q.push(t-1); if(2*t <= 200 && 2*t >= -200) q.push(2*t); } } cout << level << endl; return 0; }