运用优先队列把所有情况都入队，然后取出步数最少的。。
#include"stdio.h"
#include"string.h"
int visit[110000];
#include"queue"
using namespace std;
int n,m;
struct point
{
int x,step;
friend bool operator<(point a,point b)
{
return a.step>b.step;
}
};
int dfs()
{
priority_queue<point>q;
point cur,next;
cur.x=n;
cur.step=0;
visit[n]=1;
q.push(cur);
while(!q.empty())
{
next=q.top();
q.pop();
if(next.x==m)
return next.step;
cur.x=next.x+1;
if(cur.x<=100000&&!visit[cur.x])
{
visit[cur.x]=1;
cur.step=next.step+1;
q.push(cur);
}
cur.x=next.x-1;
if(cur.x>=0&&!visit[cur.x])
{
visit[cur.x]=1;
cur.step=next.step+1;
q.push(cur);
}
cur.x=next.x*2;
if(cur.x<=100000&&!visit[cur.x])
{
visit[cur.x]=1;
cur.step=next.step+1;
q.push(cur);
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(visit,0,sizeof(visit));
printf("%d\n",dfs());
}
return 0;
}
这个队列更省时。。
#include"stdio.h"
#include"string.h"
int visit[110000];
#include"queue"
using namespace std;
int n,m;
struct point
{
int x,step;
};
int dfs()
{
queue<point>q;
point cur,next;
cur.x=n;
cur.step=0;
visit[n]=1;
q.push(cur);
while(!q.empty())
{
next=q.front();
q.pop();
if(next.x==m)
return next.step;
cur.x=next.x+1;
if(cur.x<=100000&&!visit[cur.x])
{
visit[cur.x]=1;
cur.step=next.step+1;
q.push(cur);
}
cur.x=next.x-1;
if(cur.x>=0&&!visit[cur.x])
{
visit[cur.x]=1;
cur.step=next.step+1;
q.push(cur);
}
cur.x=next.x*2;
if(cur.x<=100000&&!visit[cur.x])
{
visit[cur.x]=1;
cur.step=next.step+1;
q.push(cur);
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(visit,0,sizeof(visit));
printf("%d\n",dfs());
}
return 0;
}