题目的要求是求到达目标位置的最少步数,根据题目特点,很显然应该用广度优先搜索来解决。根据广度搜索的特点,广搜最先扫描到得点所需要的步数即为最小步数。
提到最小步数,可能有些人会想到dp或者最短路径,用他们的确可以解决,但是dp明显比较繁琐,且写的不好还容易超时,计算了很多不必要的信息,而最短路径多是用来解决加权图的问题,对于这种最小步数的问题,广度搜索往往是最好的方法之一。下面给出源码:
#include <iostream>
using namespace std;
#define max 100001
long n,k,f[max],d[max];
bool visit[max];
void bfs()
{
long head,tail,x,y;
head=tail=0;
d[0]=n;
f[n]=0;
visit[n]=true;
while(head<=tail)
{
x=d[head];
y=x-1;
if(y>=0&&!visit[y])
{
tail++;
d[tail]=y;
f[y]=f[x]+1;
visit[y]=true;
}
y=x+1;
if(y<=max&&!visit[y])
{
tail++;
d[tail]=y;
f[y]=f[x]+1;
visit[y]=true;
}
y=x*2;
if(y<=max&&!visit[y])
{
tail++;
d[tail]=y;
f[y]=f[x]+1;
visit[y]=true;
}
if(visit[k])
break;
head++;
}
}
int main()
{
int i;
cin>>n>>k;
memset(visit,false,sizeof(visit));
bfs();
cout<<f[k]<<endl;
return 0;
}