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

算法思想：该题为典型的宽度优先搜索。具体来说，就是不断把当前猎豹可能到达的所有坐标节点压入到一个队列中，在每一次压入队列操作完毕后，立即寻找队列中所有的坐标是否已经覆盖到野猪所在的坐标，也就是目标节点，如果找到了的话就证明找到了一种最短的走法，否则将当前节点弹出队列并压入后继节点，依次往复。此外，利用一个计数器来记录走过的步数，以及为了优化搜索效率，需要对之前访问过的坐标节点作标记，以后都不必重复压入到队列中。#include#includeusing 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 Q; Q.push( n ); int cP; int nNode=1; int move=0; while( 1 ){ move++; for( int i=0 ; i=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 2

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