考察知识点：BFS、搜索
BFS常用于求最短路径，最优解等问题。通过BFS，可以减少思维难度，转化为用BFS暴力搜索出来，另外，需要知道隐式图和显式图
题目描述：
你收到通知被中南大学录取了，高兴的来到了长沙，很快你就来到了岳麓南路上，已知你的位置是N，中南大学的位置是K。为了去中南大学，你有两种移动方式：走路或者坐公交。
走路：你可以从位置X移动到X+1或者X-1
搭公交车：你可以从位置X移动到2X
每次走路或者搭公交车所需要的时间都是1分钟，你想尽快到达中南大学，所需的时间是多少呢？
输入
多组数据。
对于每组数据，输入一行，分别是N和K(0<=N,K<=100,000)
输出
对于每组数据，输出一行，所需时间
样例输入
5 17
样例输出
4
解题思路：如果我们按照常规的想法，我们会思考哪些路段走路，那些路段搭公交车，这样我们要思考的情况就很复杂。那么我们可以改用BFS进行搜索。因为此题需要找最短时间，符合BFS的应用场景。那么使用BFS的思路是从N出发，一步一步搜索，然后如果走过了位置K，那么就往回走，如果没走过，就继续往前走，每走一步时间加1，直到走到位置K。把整个过程想象成在一根数轴上，起点是N，终点是K
解题代码：
#include #include using namespace std;//我们需要一个结构体struct node{ int x,t;}p;int main(){ int n,k; while(~scanf("%d%d",&n,&k)) { //如果N>k,往回走n-k分钟就到 if(n>=k) { printf("%dn",n-k);continue; } vectorv(k*2);//默认初始是0 queue q; q.push({n,0});//起始点入队 v[n] = 1; while(!q.empty()) { p = q.front(); q.pop(); if(p.x==k) break; //枚举当前位置下一步能走的情况 else if(p.x>k){//右边 if(!v[p.x-1]){ q.push({p.x-1,p.t+1}); v[p.x-1]=1; } } else {//左边 //注意如果要回头走，必须满足第一个if的条件 if(p.x>0&&!v[p.x-1]) { q.push({p.x-1,p.t+1}); v[p.x-1]=1; } //走路 if(!v[p.x+1]) { q.push({p.x+1,p.t+1}); v[p.x+1]=1; } //坐公交 if(!v[p.x*2]){ q.push({p.x*2,p.t+1}); v[p.x*2]=1; } } } printf("%dn",p.t); } return 0;}