题目链接：POJ 3278
题意：
给出两个数字n,k。每次在一个位置p可选择先前走1步到达p+1，或者先前走p步到达2*p，或向后走一步到达p-1。问最少需要多少次移动可以从0出发到达k？
例如n=5，k=17时，最短的移动路径是：0-->5-->10-->9-->18-->17,记为4次。
思路：
用BFS搜索。每次从队列首取出一个所到达的位置，判断该位置是不是目标位置，如果不是的话，然后从该位置有三种方案选择下一位置，将符合条件的方案（剪枝）压入队列（如果不是目标位置）。开两个数组，一个用于记录该位置是否已经访问过，一个用于记录到达该位置的步骤数。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100010;queue<int> q;
int step[maxn];
bool vis[maxn];
int n, k;
int nextn, head;int bfs()
{q.push(n);step[n] = 0;vis[n] = 1;while (!q.empty()){head = q.front();//去队列首元素q.pop();for (int i = 0;i < 3;i++){//每次有三种选择，nextn是下一次位置if (i == 0) nextn = head - 1;else if (i == 1) nextn = head + 1;else nextn = head * 2;if(nextn > maxn || nextn < 0) continue;//剪枝，否则队列内元素太多了if (!vis[nextn])//该位置尚未被访问过{q.push(nextn);step[nextn] = step[head] + 1;vis[nextn] = 1;}if (nextn == k) return step[nextn];//到达目标位置}}return -1;
}
int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifwhile(cin>>n>>k){memset(vis, 0, sizeof(vis));if (n >= k) cout << n - k << endl;else cout << bfs() << endl;}return 0;
}