1.引言
我又来了！（这速度.....）
没想到吧，暑假我的速度可是能超过博尔特的（补食），不要小看了蒟蒻o(*￣︶￣*)o
废话不多说，直接start。
2.概念
okok那么好（doge），上章我们也是讲了棋盘广搜，想必你们肯定学会了（没学会也要学会），这节课我们来再讲一下普通广搜。
一般正常广搜呢都是一维（棋盘是二维），但x，y还是有滴，就是意义不大一样（等会儿再说），并且普通广搜在一般情况下不用定义dx，dy，so这俩数组可以跟我们说拜拜了┏(＾0＾)┛~
咳咳，回正题，广搜的基本框架还是那些，比如队列、vis数组以及广搜的各种方向（棋盘广搜是一个一个按方向走，而普通广搜就是按照题意在bfs内定义一个数组来存储下一步可以走的位置），所以其实可以直接套用棋盘广搜。那我们可以来写一下框架：
#include<bits/stdc++.h>
using namespace std;
int 题目输入的东西,vis[题目所给大小];
struct node{
int x,y; //x代表现在的位置，y表示步数
};
queue <node> q;
int bfs(){
q.push(node{初始位置});
vis[初始位置] = 1; //将初始位置标记为1，即避免重复
while(!q.empty()){
int x = q.front().x,y = q.front().y; //把队列中的最前元素单独提出
q.pop(); //别忘删除
if(x == 终止条件) return ...; //这里判断是否达到题目要求，达到则返回值（或者将bfs改为void类型并输出所给内容）
int x_n[可以走的位置数] = {第一种走法、第二种走法...}; //相当于棋盘广搜中的dx，dy，只不过可以直接算出下一步的位置
for(int i = 0;i <= 可以走的位置数-1;i++){ //遍历每种走法
int x_next = x_n[i]; //当下一步x的位置是x_n[i]时
if(x_next >= 1 && x_next <= n && !vis[x_next] && ...){ //加上各种判断条件
q.push(node{x_next,y + 1}); //加入队列等待搜索
vis[x_next] = 1; //标记已走过，避免重复
}
}
}
}
int main()
{
——————题目要求输入——————
......
cout << bfs();
//或者bfs(); + 题目所给输出格式
return 0;
}同样，棋盘广搜不会的也可以加上dx，dy来套用（别告诉我不会改，上章代码对照就行了）。
好，框架给了，来尝试一下题目：
3.演练
1.奇怪的电梯
题目描述
有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第ii层楼(1≤i≤N)有一个数字Ki(0≤Ki≤N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3,3,1,2,5代表了Ki(K1=3,K2=3,...)，从1楼开始。在1楼，按"上"可以到4楼，按"下"是不起作用的，因为没有−2楼。那么，从A楼到B楼至少要按几次按钮呢？
输入描述
共二行。
第一行为3个用空格隔开的正整数，表示N,A,B(1≤N≤200,1≤A,B≤N)。
第二行为N个用空格隔开的非负整数，表示Ki。
输出描述
一行，即最少按键次数，若无法到达，则输出−1。
样例1
输入
5 1 5 3 3 1 2 5
输出
3
样例2
输入
12 10 1 1 1 1 1 1 1 1 1 1 1 1 1
输出
9
这题一看就十分简单，我们来大致套一下：
首先数组范围是N的大小，也就是200，保险一点开205；
其次我们的初始位置中因为题目要求是从A楼开始，那么初始位置的x就是A的层数，y就是0（没开始走呢），同时vis[a] = 1也就不用多说了吧；
再者因为终止条件是到B楼，所以呢，终止条件就不用多说了，最后因为是返回按几次，so返回y就行啦；
最后，我们发现每一步都是有两种可能性的，第一种是上k[i]层，第二种是下k[i]层，那么x_n里的两种情况不需我多说了吧~；
当然，if的条件只用那三个就足够了，因此不用增加。
分析到这里，我们再加上输入，完美竣工：
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n,a,b;
int k[205],vis[205];
struct node{
int x,y;
};
queue <node> q;
int bfs(){
q.push(node{a,0});
vis[a] = 1;
while(!q.empty()){
int x = q.front().x,y = q.front().y;
q.pop();
if(x == b) return y;
int x_n[2] = {x + k[x],x - k[x]};
for(int i = 0;i <= 1;i++){
int x_next = x_n[i];
if(x_next >= 1 && x_next <= n && !vis[x_next]){
q.push(node{x_next,y + 1});
vis[x_next] = 1;
}
}
}
return -1; //题目要求如果不能达到就输出-1，这里就是为了应对这种条件，当然谁知道这电梯怎么还有楼层到不了呢，质量未必太差了doge~
}
int main()
{
cin >> n >> a >> b;
for(int i = 1;i <= n;i++) cin >> k[i];
cout << bfs();
return 0;
}太简单啦！！！
2.抓住那头牛
题目描述
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。农夫有两种移动方式：1、从X移动到X−1或X+1，每次移动花费一分钟2、从X移动到2×X，每次移动花费一分钟。假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入描述
两个整数，N和K。
输出描述
一个整数，农夫抓到牛所要花费的最小分钟数。
样例1
输入
5 17
输出
4
提示
从5向左走到4，从4变成8，从8变成16，然后16向右走一步到17
这道题呢，深搜能做，但超不超时嘛...你自己看吧。
贪心的话，其实不好做，because这题不是一直快速接近就可以的。
比如样例，贪心的话肯定是先从5到10，再连续+7，得到8；而5到10到20再回，也是5，所以别想着那么容易啦。
这道题做法还是广搜套模板，起始位置为n，终止位置为k，x_n中分别为那三种情况（懂吧），
至于for的边界则改为0 ≤ n ≤ 1e5，所以懂了吧（阿巴阿巴......）
这样直接套出来了，三！二！一！上代码！（嗷呜嗷呜......）
#include <bits/stdc++.h>
using namespace std;
int n,k,vis[200005];
struct node{
int x,y;
};
queue <node> q;
int bfs(){
q.push(node{n,0});
vis[n] = 1;
while(!q.empty()){
int x = q.front().x,y = q.front().y;
q.pop();
if(x == k) return y;
int x_n[3] = {x - 1,x + 1,2 * x};
for(int i = 0;i <= 2;i++){
int x_next = x_n[i];
if(x_next >= 0 && x_next <= 1e5 && !vis[x_next]){
q.push(node{x_next,y + 1});
vis[x_next] = 1;
}
}
}
return -1;
}
int main(){
cin >> n >> k;
cout << bfs();
}下一题，太简单了。（语句歧义，是病句doge）
3.青蛙跳木桩
题目描述
河面上有N个木桩排成一排，且每个木桩上都有一个数字，木桩上的数字表示青蛙从当前木桩一次最多可跳跃的木桩个数（例如木桩上的数字为2，青蛙可以跳跃一个木桩也可以跳跃两个木桩）。青蛙只能从第一个木桩向最后一个木桩的方向跳跃。请你帮助青蛙计算出从第一个木桩跳跃到最后一个木桩最少需要跳跃几次。
例如：N=5，5个木桩上的数字分别为2，1，5，1，3。
第一次跳跃，青蛙从第一个木桩跳跃到第三个木桩，共跳了2个木桩；
第二次跳跃，青蛙从第三个木桩跳跃到最后一个木桩，共跳了2个木桩；
故最少需要跳跃2次可到达最后一个木桩。
输入描述
第1行，1个正整数N
第2行，N个正整数a1,a2,⋯ ,aN，表示每个木桩上的数
输出描述
输出1个数，表示最少跳跃次数。
样例1
输入
5 2 1 5 1 3
输出
2
样例2
输入
10 4 1 3 4 3 4 3 3 3 2
输出
3
样例3
输入
17 2 1 4 3 1 1 1 1 6 5 1 1 2 3 2 4 1
输出
6
样例4
输入
6 2 5 1 1 1 1
输出
2
提示
1≤N≤1e5
1≤ai≤100
这道题其实也不难，来分析一下：
首先if的条件中x_next >=1其实可以删去，因为只让往后跳嘛doge；至于往前跳几步就不能再用x_n数组了，毕竟你不知道它有几种可能啊！！！
所以学了棋盘广搜的我们就要使用棋盘的更新方法：for循环遍历可能，每种可能加上原来的位置后即可。
最后我们要搞清一个概念，因为有人可能问：你这样遍历又怎么会一定是最短的呢？一旦终止时y的值不是最少的咋办？总不能交个错误答案吧！
其实这个问题很简单：步数最少不代表广搜层数划的少么？既然如此，那么最先遍历到的满足条件的就肯定是最短的！（举个栗子：一种情况3步到达，一种情况4步到达，那么根据广搜的遍历方法，就能知道3步到的方法（相当于遍历到第3层）会比4步到（相当于遍历到第4层）的先遍历出，于是就能得到答案3）
so这道题变得十分简单：
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,vis[100005],a[100005];
struct node{
int x,y;
};
queue <node> q;
int bfs(){
q.push(node{1,0});
vis[1] = 1;
while(!q.empty()){
int x = q.front().x,y = q.front().y;
q.pop();
if(x == n) return y;
for(int i = 1;i <= a[x];i++){
int x_next = x + i;
if(x_next <= n && !vis[x_next]){
q.push(node{x_next,y + 1});
vis[x_next] = 1;
}
}
}
return -1; //懂么
}
int main(){
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i];
cout << bfs();
return 0;
}撒花！
4.习题
来吧，还是老东西，难度依旧上档次：
1.最小的移动步数
题目描述
一个一维数轴上有n+1个格点，坐标从0到n。
你一共有两种移动方式：1、从x移动到x−1或者x+1，每次移动算作一步。2、从x移动到ax，每次移动也算作一步。特别的，当你在0这个位置的时候，只能选择移动到1这个位置。此外你在移动的过程中不可以走出这n+1个格点。
刚开始的时候你在0这个位置，现在小A想知道你走到1~n这n个位置中的每一个位置需要的最小步数是多少。
输入描述
第一行一个正整数n。
接下来一行n个正整数，第i个数字是ai。
输出描述
共一行，一共n个用空格分隔的数字，第i个数表示从0走到i最少需要多少步。
样例1
输入
3 3 1 2
输出
1 2 2
提示
1≤n≤105
1≤ai≤n
所有输入均为整数。
2.质数的数字转化
题目描述
现在小A给你两个四位质数a和b，你需要通过最少的操作次数将a变为b。
每次操作你只能改变当前数的其中一位数字，并且每次操作后，必须保证新的数字仍然是一个质数。
例如：将1033变为8179，最少需要6次操作，具体为:
1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179
如果无法使得a变成b，输出-1。
输入描述
一共一行包含两个四位质数a和b。
输出描述
一行一个数表示最少的操作数，如果无法做到，输出−1。
样例1
输入
1999 8999
输出
1
提示
1000≤a,b≤9999
题目保证a和b一定是质数。
5.小结
至此，广搜的内容咱们算是学会了，所以我们有一次多了一种新的解题方法（好像是废话，但我没有证据），所以886！记得来看《贪心算法（基础算法）》！
上一章：广度优先搜索算法1（棋盘篇） 下一章：贪心算法（未完工）