这一题是练习广度优先搜索很好的例题，在很多广搜教学中经常用到，放在这里供学习搜索算法的孩纸们看看= =

 

---

 

 

题目大意：一维数轴上，农夫在N点，牛在K点，假定牛不会移动，农夫要找到这头牛只能够进行以下三种移动方法

• 2*N-跳跃到两倍于自己所在的位置
• N+1 -右移一位
• N -1 -左移一位

 

BFS解法解析：按照移动步数依次遍历队首，pop掉，并拓展出下一步所有可走位置并依次压入队列(不懂的孩纸们找度娘，很基础的数据结构)中，在这里为Code方便，我使用STL中的queue。

 

---

 

 

Code如下：

 

1 //从N到K 2 //要么N*2,要么N+1或者N-1 3 //Time: 94 Ms 4 #include
     
       5 #include
      
        6 #include
       
         7 #include
        
          8 using namespace std; 9 const int MAXN=100005;10 int n,k;    //所在位置，需到达位置(一维)11 int time[MAXN];12 int v[MAXN];13 void bfs()14 {15     int cur,temp;16     queue
         
           q;17     q.push(n);18     while( !q.empty() )19     {20         cur = q.front();21         q.pop();22         v[cur] = 1;23         if(cur == k)24         {25             cout<
          
           <
           
            =0 && temp < MAXN && !v[temp])39 {40 q.push(temp);41 time[temp] = time[cur]+1;42 v[temp] = 1;43 }44 }45 }46 }47 int main()48 {49 cin>>n>>k;50 if(n<=k)51 bfs();52 else53 cout<
            
             <