BFS（广度优先搜索）---抓住那头牛

阳光穿透心脏的1/2处 2023-06-30 10:43 57阅读 0赞

# 题目描述： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]

# 样例输入 #

1 89

# 样例输出 #

# 代码： #

#include <sstream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    #include <string>
    #include <queue>
    #include <stack>
    #include <map> 
    #include <set>
    
    #define _for(i,a,b) for(int i=a;i<b;i++)
    #define _unfor(i,a,b) for(int i=a;i>=b;i--)
    #define RI(a) scanf("%d",&a)
    #define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
    #define mset2(a,val,n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=val;
    #define FI freopen("D:\\in.txt","r",stdin)
    #define FO freopen("D:\\out.txt","w",stdout)
    
    using namespace std;
    typedef long long LL;
    /*-------下面为主要代码-------*/
    
    int N,K;
    const int MAXN = 100000;
    int visited[MAXN+10]; //判重标记，visited[i] = true 表示 i已经扩展过
    struct Step //设置 Step 用于存储信息
    { 
    	int x; //当前位置
    	int steps; //到达 x 所需的步数
    	Step(int xx,int s):x(xx),steps(s) { } //
    };
    queue<Step> q; //队列 q
    int main()
    { 
    	cin >> N >> K;
    	memset(visited,0,sizeof(visited));
    	q.push(Step(N,0)); //将 Step 加入队列（尾）中
    	visited[N] = 1;
    	while(!q.empty()) //记住用这种方式
    	{ 
    		Step s = q.front();
    		if( s.x == K )
    		{  //找到目标
    			cout << s.steps <<endl;
    			return 0;
    		}
    		else
    		{ 
    			if( s.x - 1 >= 0 && !visited[s.x-1] )
    			{ 
    				q.push(Step(s.x-1,s.steps+1));
    				visited[s.x-1] = 1;
    			}
    			if( s.x + 1 <= MAXN && !visited[s.x+1] )
    			{ 
    				q.push(Step(s.x+1,s.steps+1));
    				visited[s.x+1] = 1;
    			}
    			if( s.x * 2 <= MAXN &&!visited[s.x*2] )
    			{ 
    				q.push(Step(s.x*2,s.steps+1));
    				visited[s.x*2] = 1;
    			}
    			q.pop(); //前面加一个 Step 后面就删除一个 Step
    		}
    	}
    	return 0;
    }

# 解析： #

### 1、关于 queue 的基本函数 ###

<table> 
 <thead> 
  <tr> 
   <th>queue</th> 
   <th>功能</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size（）</td> 
   <td>返回队列中的元素个数</td> 
  </tr> 
  <tr> 
   <td>front（）</td> 
   <td>返回队头的元素</td> 
  </tr> 
  <tr> 
   <td>back（）</td> 
   <td>返回队尾元素</td> 
  </tr> 
  <tr> 
   <td>pop（）</td> 
   <td>删除队头的元素</td> 
  </tr> 
  <tr> 
   <td>push（<strong>g</strong>）</td> 
   <td>向队尾中添加元素 <strong>g</strong></td> 
  </tr> 
  <tr> 
   <td>empty（）</td> 
   <td>在队列没有元素时返回 <strong>true</strong></td> 
  </tr> 
 </tbody> 
</table>

##### 其用法与 vector 类似，可参考 [C++ STL库 容器与方法][C_ STL_] 中的 Vector 容器 #####

#### 2、由于在 C++ 中 struct 和 class 最主要的区别是默认访问权限和继承方式不同，而其他方面的差异很小，所有在算法竞赛中使用较为简单的 struct ####

##### 3、其实代码整体上的 queue< Step> q 中可以理解为只有两个元素（Step），一个是从一开始加入的，另一个是用于搜索的，而这个用于搜索的是根据队列的第一个 Step 改进而成的，当改完后用 q.pop（）删除第一个 Step，自己就成为了第一个 Step，并继续第二轮搜索，直到找到目标 #####

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200117013052651.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[C_ STL_]: https://blog.csdn.net/CourserLi/article/details/103027046