在一个长度为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;
//向前走,坐标+1
y=x+1;
if(!st[y]&&y>=1&&y<=n){
st[y]=true;
dfs(y,step+1);
st[y]=false;
}
//向后走,坐标-1
y=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;
}