题目见链接:原题
大致题意:
给定两个整数n和k
通过 n+1或n-1 或n*2 这3种操作，使得n==k
输出最少的操作次数
解题思路：
用BFS遍历，只需得到一个最小解就行。
注意的地方：
1 剪枝。直接广搜一样等着RE吧= = ，判断下一步是否超出边界，即大于100000或者小于0，否则RE。
BFS有固定的解题思路：
定义一个队列，然后取队头元素，从队头周围开始搜索，搜索结果入队，别忘记了rear指针和front指针加1。一直循环以上操作，直到rear < =front。
BFS最重要的是对边界的判断，否则容易超时或错误。
#include <iostream> using namespace std; const int MAXSIZE = 100005;// 数组大小 int visit[MAXSIZE]; // 标记数组 int N, K; int head; typedef struct{ int step; int x; }Point; typedef struct{ Point val[MAXSIZE]; int front; int rear; }Queue; // 定义一个队列 int bfs(int start) { Queue queue = {{0}, 0, 0}; queue.val[0].step = 0; // 起始元素入队 queue.val[0].x = start; queue.rear++; visit[queue.val[0].x] = 1; int next; while(queue.rear > queue.front) { head = queue.val[queue.front].x; // 取队头元素 for(int i = 0; i < 3; i++) { if(i == 0) { next = head - 1; } else if(i == 1) next = head + 1; else next = 2 * head; if(next > 100000 || next < 0) continue; // 边界判断 if(!visit[next]) { queue.val[queue.rear].x = next; queue.val[queue.rear].step = queue.val[queue.front].step + 1; queue.rear ++; visit[next] = 1; } if(next == K) // 终止条件判断 { return queue.val[queue.rear - 1].step; } } queue.front++; // 千万别忘记头指针加一，血的教训 } return 0; } int main() { while(cin>>N>>K) { memset(visit,0,sizeof(visit)); if(N == K) { cout << 0 << endl; } else{ cout << bfs(N) << endl; } } return 0; }
