Question

这道题目怎么做？求算法！

猎豹和野猪在同一条直线上，他们的坐标分别是 x 和 y，x 是小于等于 y的。
现在猎豹有两种跑法：
1．跑动一格，就是从 x 到x+1 或者x-1；
2．跑动一倍，就是从 x 到2*x。
现在请你找出最少要几步捉到野猪。
数据输入
输入第 1 行给出两个正整数 x、y（0<x<=y<=100000），分别表示猎豹的坐标和野猪的坐标。
数据输出
输出只有 1行，给出最少步数。
例：5 17
4

Answer 1

思想：每一步都比较两种跑法那一种更接近目标，用一个自增计数器计算步数。

Answer 2

算法思想：

该题为典型的宽度优先搜索。

具体来说，就是不断把当前猎豹可能到达的所有坐标节点压入到一个队列中，在每一次压入队列操作完毕后，立即寻找队列中所有的坐标是否已经覆盖到野猪所在的坐标，也就是目标节点，如果找到了的话就证明找到了一种最短的走法，否则将当前节点弹出队列并压入后继节点，依次往复。

此外，利用一个计数器来记录走过的步数，以及为了优化搜索效率，需要对之前访问过的坐标节点作标记，以后都不必重复压入到队列中。

#include<iostream>
#include<queue>
using namespace std;

const int MAXN=100000;

bool visited[MAXN+1];
int n,k;
int Bfs()
{

if( n==k ) return 0;

memset( visited,false,sizeof(visited) );
visited[n]=true;

queue<int> Q;
Q.push( n );

int cP;
int nNode=1;
int move=0;

while( 1 ){
move++;
for( int i=0 ; i<nNode ; i++ ){
cP=Q.front();
Q.pop();
if( cP-1>=0&&!visited[cP-1] ){
if( cP-1==k )
return move;

visited[cP-1]=true;
Q.push( cP-1 );
}
if( cP+1<=MAXN&&!visited[cP+1] ){
if( cP+1==k )
return move;

visited[cP+1]=true;
Q.push( cP+1 );
}
if( 2*cP<=MAXN&&!visited[2*cP] ){
if( 2*cP==k )
return move;

visited[2*cP]=true;
Q.push( 2*cP );
}
}

//debug here , size is chaging , not 3^j
nNode=Q.size();

}

}

int main()
{
while( cin>>n>>k ){

cout<<Bfs()<<endl;

}
return 0;

}

Answer 3

这个题不难,自己写吧