网站设计与wap网站开发技术,做球形全景的网站,做网站的公司创业,吴江盛泽建设局网站在一个长度为n的坐标轴上#xff0c;小S想从A点移动B点。 他的移动规则如下#xff1a; 向前一步#xff0c;坐标增加1。 向后一步#xff0c;坐标减少1。 跳跃一步#xff0c;使得坐标乘2。 小S不能移动到坐标小于0或大于n的位置。 小S想知道从A点移动到B点的最少步数是多… 在一个长度为n的坐标轴上小S想从A点移动B点。 他的移动规则如下 向前一步坐标增加1。 向后一步坐标减少1。 跳跃一步使得坐标乘2。 小S不能移动到坐标小于0或大于n的位置。 小S想知道从A点移动到B点的最少步数是多少你能帮他计算出来么 输入格式 第一行输入三个整数nAB分别代表坐标轴长度起始点坐标终点坐标。0ABn50000 输出格式 输出一个整数占一行代表小S要走的最少步数。 样例输入 10 2 7 样例输出 3 dfs深度优先时间复杂度会比较高这里仅供理解题目
#includeiostream
using namespace std;
const int N50005;
bool st[N];
int n,A,B;
int ans;
void dfs(int x,int step){if(xB){//结束条件 ansstep;return;}int y;//向前走坐标1yx1;if(!st[y]y1yn){st[y]true;dfs(y,step1);st[y]false;}//向后走坐标-1yx-1;if(!st[y]y1yn){st[y]true;dfs(y,step1);st[y]false;}//跳跃坐标*2 yx*2;if(!st[y]y1yn){st[y]true;dfs(y,step1);st[y]false;}
}
int main(){cinnAB;dfs(A,0);coutansendl;return 0;
}
bfs广度优先 #includeiostream
#includequeue
using namespace std;
const int N50005;
bool st[N];
typedef struct point{int x;int step;
}point;
queuepoint q;
int n,A,B;void bfs(){while(q.size()){point pq.front();if(p.xB){break;}point next;int a;//向前走坐标1 ap.x1;if(!st[a]a1an){next.xa;next.stepp.step1;q.push(next);//入队st[a]true; }//向后走坐标-1 ap.x-1;if(!st[a]a1an){next.xa;next.stepp.step1;q.push(next);//入队st[a]true; }//跳跃坐标*2 ap.x*2;if(!st[a]a1an){next.xa;next.stepp.step1;q.push(next);//入队st[a]true; }q.pop(); }
}
int main(){cinnAB;point start;start.xA;start.step0;q.push(start);bfs();coutq.front().stependl;return 0;
}
