一维坐标的移动（bfs）

在一个长度为n的坐标轴上，小S想从A点移动B点。

他的移动规则如下：

向前一步，坐标增加1。

向后一步，坐标减少1。

跳跃一步，使得坐标乘2。

小S不能移动到坐标小于0或大于n的位置。

小S想知道从A点移动到B点的最少步数是多少，你能帮他计算出来么？

输入格式

第一行输入三个整数n，A，B，分别代表坐标轴长度，起始点坐标，终点坐标。（0<=A，B<=n<=50000）

输出格式

输出一个整数占一行，代表小S要走的最少步数。

样例输入

10 2 7

样例输出

3

dfs深度优先（时间复杂度会比较高，这里仅供理解题目）

#include<iostream>
using namespace std;
const int N=50005;
bool st[N];
int n,A,B;
int ans;
void dfs(int x,int step){if(x==B){//结束条件 ans=step;return;}int y;//向前走，坐标+1y=x+1;if(!st[y]&&y>=1&&y<=n){st[y]=true;dfs(y,step+1);st[y]=false;}//向后走，坐标-1y=x-1;if(!st[y]&&y>=1&&y<=n){st[y]=true;dfs(y,step+1);st[y]=false;}//跳跃，坐标*2 y=x*2;if(!st[y]&&y>=1&&y<=n){st[y]=true;dfs(y,step+1);st[y]=false;}
}
int main(){cin>>n>>A>>B;dfs(A,0);cout<<ans<<endl;return 0;
}

bfs广度优先

 

#include<iostream>
#include<queue>
using namespace std;
const int N=50005;
bool st[N];
typedef struct point{int x;int step;
}point;
queue<point> q;
int n,A,B;void bfs(){while(q.size()){point p=q.front();if(p.x==B){break;}point next;int a;//向前走，坐标+1 a=p.x+1;if(!st[a]&&a>=1&&a<=n){next.x=a;next.step=p.step+1;q.push(next);//入队st[a]=true; }//向后走，坐标-1 a=p.x-1;if(!st[a]&&a>=1&&a<=n){next.x=a;next.step=p.step+1;q.push(next);//入队st[a]=true; }//跳跃，坐标*2 a=p.x*2;if(!st[a]&&a>=1&&a<=n){next.x=a;next.step=p.step+1;q.push(next);//入队st[a]=true; }q.pop(); }
}
int main(){cin>>n>>A>>B;point start;start.x=A;start.step=0;q.push(start);bfs();cout<<q.front().step<<endl;return 0;
}