2013程序设计实现之广搜作业 A

/**

***= =，好吧我来翻译一下，就是有2个数A，B。A可以+1，-1，*2来改变自己的值，上面三种情况都算作操作+1。求A=B所用的最少的操作数。。。。。（0<A,B<100000）.
----此题来自百练poj
A:Catch That Cow
查看 提交 统计 提问
总时间限制: 2000ms 内存限制: 65536kB
描述
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately.
 He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000)
 on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

输入
Line 1: Two space-separated integers: N and K
输出
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

*/
#include<iostream>
#include<queue>
#include<string.h>//memset()

using namespace std;

int getMinStepsByBFS(int n,int k){
     int xSteps[100001];
     memset(xSteps,0,sizeof(xSteps));//这里将所有的该范围内的数都包含，内容为0即未操作过，否则在原来的基础上+1
     queue<int> points;//此队列是用来存要进行操作的点
     points.push(n);
     while(!points.empty()){
                 int x = points.front();
                 if(x == k){
                      return xSteps[k];//广度搜索搜一次就能搜到最优解，因为他是在所有操作数相同的情况下最先搜到的
                      }else{
                            points.pop();
                            for(int i = 0;i < 3;i++){
                                    switch(i){
                                              case 0 :
                                                   if(x-1>= 0 && !xSteps[x-1] && x-1!=n){
                                                                  xSteps[x-1] = xSteps[x]+1;
                                                                  points.push(x-1);
                                                                  }
                                                   break;
                                              case 1 :
                                                   if(x-1 <= 100000 && !xSteps[x+1] && x+1!=n){
                                                                  xSteps[x+1] = xSteps[x]+1;
                                                                  points.push(x+1);
                                                                  }
                                                   break;
                                              case 2 :
                                                   if(2*x <= 100000 && !xSteps[2*x] && 2*x!=n){
                                                                  xSteps[2*x] = xSteps[x]+1;
                                                                  points.push(2*x);
                                                                  }
                                                   break;
                                              default :
                                                      cout<<"error"<<endl;
                                              }
                                    }
                            }
                 }
     }
   
int main(){
    int n,k;
    cin>>n>>k;
    if(n>=0 && n<=100000 && k>=0 && k<= 100000){
        cout<<getMinStepsByBFS(n,k)<<endl;
    }
    system("pause");
    return 0;
        }