本文主要是介绍我跳我跳我跳跳跳 广度优先搜索,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这是一道广度搜索的变形体,刚开始没反应过来;
题目描述
有一条直线,上有n个点,编号从0到n-1。当小A站在s点处,每次可以往前跳到s+1,也可以往前跳到s-1(当s-1 >= 0时),也可以调到2*s处。现在问小A最少跳多少次才能跳到点e处。
输入
多组输入。每组输入两个整数s,e(0 <= s,e <= 100,000)。n趋于无穷大。
输出
输出小A从s跳到e的最小次数。
示例输入
5 17
示例输出
4
#include<stdio.h>
#include<string.h>
int q[210000];
int a[210000];
int b[210000];
void bfs(int s,int e)
{int low=0 ,top=0,now,next;q[top++]=s;a[s]=0;b[s]=1;while(low<top){now=q[low++];if(now==e){printf("%d\n",a[now]);return ;}next=now-1;if( next >= 0 &&next < 210000 && b[next] != 1){q[top++]=next;a[next]=a[now]+1;b[next]=1;}next=now+1;if( next >= 0 &&next < 210000 && b[next] != 1){q[top++]=next;a[next]=a[now]+1;b[next]=1;}next=now*2;if( next >= 0 &&next < 210000 && b[next] != 1){q[top++]=next;a[next]=a[now]+1;b[next]=1;}}
}
int main()
{int s,e;while(scanf("%d%d",&s,&e)!=EOF){memset(b,0,sizeof(b));bfs(s,e);}return 0;
}
这篇关于我跳我跳我跳跳跳 广度优先搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!