在我们日常刷题的过程中，我们会通过遍历来获取自己想要的数组，搜索算法就是典型的一种。
而搜索算法中也分深搜（DFS），广搜（BFS）,而今天，我们来说说广搜。
什么是广搜
广搜全称叫广度优先搜索，或叫宽度优先搜索，简称BFS。人如其名，他不像深搜一路干到底，而是一层一层的搜索，如图
当然，广搜有很多种，这只是广搜和二叉树的结合，不过大体就是像这样，一层一层的搜索
广搜原理及其伪代码
如上图，是广搜全过程（无重复搜索）
我来给大家解读下
刚开始时是1号位，由于广搜是一层层的搜索，所以搜完2号位后不能着急搜2号位的其他点，而是要把1号位能搜完的全部搜完，于是我们搜3号位。这时1号位搜完了，所以我们可以搜其他位了，我们可以先搜3号位，同搜1号位，4号位和5号位搜完了…直到最后61号位和60号位搜完了，到62号位了，最后结束。
【分析】我们口述时是直接更换搜索位置的，这对于我们人来说很轻松，但是大家想过没有，这用c++该怎么实现呢？其实很简单，用数组模拟就行，用一个变量记录现在搜的是谁，如果搜完了，就跳到下一位。
代码如下（注：此代码只是表达思路，并不是伪代码）：
int ab[1050];
int head=0;
if(搜完了){
head++;
}
else{
for(){
继续搜索 加入数据
}
}
不过虽然数组模拟通俗易懂，但对于某些情很极端，如你要加入1千万的数据，数组就存不下了，对于这种数组存不下的情况该怎么办呢？这时，我们得先冷静下来，思考，为什么数组存不下，就是因为删除的部分没有删除数据，只要把前面的数删了，问题就解决了，哎！恰好c++的STL里面的队列可以解决此问题，而且和数组差不多，甚至会比数组模拟更好用
好，看代码（注：此代码只是表达思路，并不是伪代码）
queue<int>q;
初始化
如果队列不为空{
int f=q.front();q.pop();//弹出
if(满足答案){
return ...;
}
搜索{
if(满足条件){
q.push(...);
}
}
}
好的我们终于分析完了，总结：广搜一般用队列，如果数据量较小，就用数组模拟（尽量用队列），
如果队列不为空（就是没搜完）就继续搜，搜完一个弹出队列，如果满足答案就返回（BFS函数大多是用返回值int），否则慢慢搜答案。对于搜到的答案如果满足条件就入队
好的伪代码如下
int bfs(变量){
queue<类型>q;
初始化
while(!q.empty()){ //队列不为空
类型 f=q.front(),q.pop();
if(判断能否返回)
{
return ; //返回
}
for(枚举(搜索)){
判断{
初始化搜索结果
q.push(...); //加入
如果能返回就直接返回
}
}
}
return -1; //返回不了
}
广搜经典例题
知道广搜原理后就可以上手了！
1330：【例8.3】最少步数
【题目描述】
在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100×100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。
【输入】
A、B两点的坐标。
【输出】
最少步数。
【输入样例】
12 16
18 10
【输出样例】
8
9
【分析】很明显是道广搜题（因为我们需要多重考虑），重！！！：我们在搜索时一定要方向数组，而且也要标记数组，毕竟会走重复路就会超时（亲测）。这时我们也要用到结构体了，因为考虑到了步数，位置，我们需要结构体里的变量标记，不然得至少开三维数组
#include<bits/stdc++.h>
using namespace std;
int xy[][2]={{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{2,2},{2,-2},{-2,-2},{-2,2}};
//方向数组与标记数组
int flag[105][105];
//结构体
struct node{
int x,y;
int step;//步数
};
int bfs(int x,int y){
queue<node>q;
//初始化
node cs;
flag[x][y] = 1;
cs.step = 0 , cs.x = x , cs.y = y;
q.push(cs);
while(!q.empty()){
node f = q.front(); q.pop();
if(f.x == 1 && f.y == 1){
return f.step;
}
for(int i = 0;i < 12;i++){//搜索
int xx = f.x + xy[i][0];
int yy = f.y + xy[i][1];
//数据判断
if(xx >= 1 && xx <= 100 && yy >= 1 && yy <= 100 && flag[xx][yy] == 0)
{
node nw;
flag[xx][yy] = 1;
nw.x = xx , nw.y = yy , nw.step = f.step + 1;
if(xx == 1 && yy == 1){
return nw.step;
}
q.push(nw);
}
}
}
}
int main()
{
int x,y;
cin >> x >> y;
cout << bfs(x , y) << endl;
memset(flag,0,sizeof(flag)); //调用俩次，flag清0
cin >> x >> y;
cout << bfs(x , y) << endl;
return 0;
}
1254：走出迷宫
【题目描述】
当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。
假设你已经得到了一个n×m
的迷宫的图纸，请你找出从起点到出口的最短路。
【输入】
第一行是两个整数n
和m
(1≤n,m≤100
)，表示迷宫的行数和列数。
接下来n
行，每行一个长为m
的字符串，表示整个迷宫的布局。字符‘.’表示空地，‘#’表示墙，‘S’表示起点,‘T’表示出口。
【输出】
输出从起点到出口最少需要走的步数。
【输入样例】
3 3
S#T
.#.
…
【输出样例】
6
【分析】经典广搜，方向数组，标记数组，大力枚举，结构体一条龙
#include<bits/stdc++.h>
using namespace std;
int n,m;
int flag[105][105]; //标记数组
char mp[105][105];
int dx[] = {0 , 0 , 1 , -1}; //方向数组
int dy[] = {1 , -1 , 0 , 0};
struct node{ //结构体
int x,y;
int step;
};
int bfs(int lx,int ly,int zx,int zy){
queue<node>q;
//初始化
node g;
flag[lx][ly] = 1;
g.x = lx,g.y = ly,g.step = 0;
q.push(g);
while(!q.empty()){
node f = q.front();
q.pop();
if(f.x == zx && f.y == zy){ //答案判断
return f.step;
}
//大力出奇迹
for(int i = 0;i < 4;i++){
int fx = f.x + dx[i];
int fy = f.y + dy[i];
//范围判断
if(fx >= 1 && fx <= n && fy >= 1 && fy <= m && flag[fx][fy] == 0 && mp[fx][fy] != '#')
{
flag[fx][fy] = 1;
node now;
now.x = fx , now.y = fy , now.step = f.step + 1;
q.push(now);
if(fx == zx && fy == zy){ //答案判断
return f.step + 1;
}
}
}
}
return -1;
}
int main()
{
cin >> n >> m;
int sx,sy,zx,zy;
for(int i = 1 ;i <= n;i++){
for(int j = 1;j <= m;j++){
cin>>mp[i][j];
if(mp[i][j] == 'S'){ //拿下起点位置
sx=i;
sy=j;
}
if(mp[i][j] == 'T'){ //拿下终点位置
zx=i;
zy=j;
}
}
}
cout << bfs(sx,sy,zx,zy);
return 0;
}
数字转换
给你两个数s,t, 从s开始，每次从小于当前数的质因子中挑选一个数加给当前数，问最少加几次能到达t
输入
第一行输入一个整数T，表示测试组数
接下来T行每行两个整数s,t
输出
对于每组测试数据输出一个最小步数，如果无法到达，输出-1
具体格式见样例输出
样例
输入 1
2
6 12
6 13
输出 1
Case 1: 2
Case 2: -1
提示
约定：
T<=500,1<=s<=100,1<=t<=1000
【分析】这里已经不是搜索题了，但是仍要用广搜的思想（一层层枚举），不过值得注意的是，这里需要用素数筛法+广搜
#include<bits/stdc++.h>
using namespace std;
int s,t;
const int N=1010;
int flag[N];
void init(){ //素数筛
flag[1]=1;
for(int i=2;i<N;i++){
if(flag[i]==0){
for(int j=i+i;j<N;j+=i){
flag[j]=1;
}
}
}
}
int vis[N],dis[N];//vis标记数组，dis答案数组
int bfs(int s,int t){
queue<int>q;
q.push(s);
vis[s]=1;
dis[s]=0;
while(!q.empty()){
int f=q.front();
q.pop();
if(f==t){
return dis[t];
}
for(int i=2;i*i<=f;i++){
if(f%i==0&&flag[i]==0){
int x=i;
if(f+x<=t&&vis[f+x]==0){
vis[f+x]=1;
q.push(f+x);
dis[f+x]=dis[f]+1;
}
}
if(f%i==0&&f/i!=i&&flag[f/i]==0){
int x=f/i;
if(f+x<=t&&vis[f+x]==0){
vis[f+x]=1;
q.push(f+x);
dis[f+x]=dis[f]+1;
}
}
}
}
return -1;
}
int main()
{
init();
int T,ca=1;
cin>>T;
while(T--){
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis)); //归0
cin>>s>>t;
cout<<"Case "<<ca<<": "<<bfs(s,t)<<"\n";
ca++;
}
return 0;
}
营救计划
易错题警告！！！
在一个n∗m的迷宫里，有一个萌新被困住了，你作为一个久经码场的战士，决定去营救萌新。地图中还会有一些守卫，你必须打败守卫才能通过守卫所在的位置，打败守卫需要花费1分钟，移动一步需要花费一分钟，每次你只能往上下左右某个方向移动一步。问你最少需要花费多少时间才能救到萌新。
输入
第一行输入两个整数 n,m
接下来n行每行输入m个字符
'#'代表障碍物，无法直接通过
'.'代表空地，可以直接通过
'G’代表守卫，你需要打败他才能通过
'M’代表萌新所在的位置
'@'表示你所在的位置
输出
如果可以营救到萌新，就输出最少需要花费的分钟数
如果不可以，输出“You can’t save Mengxin”
样例
输入 1
7 8
#.#####.
#.M#…@.
#…#G…
…#…#.#
#…##…
.#…
…
输出 1
13
输入 2
2 2
M.
G@
输出 2
2
提示
1<=n,m<=200
【分析】经典广搜，分析什么？于是，一顿小连招，你会，发现错了！为什么错了呢，这是经典广搜，不过是他却是考到了广搜->状态，我们只需分类讨论就行了
#include<bits/stdc++.h>
using namespace std;
const int N=222;
int n,m;
int dis[N][N][2]; //状态数组
int vis[N][N][2];
char mp[N][N];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
struct node{
int x,y,flag;
};
int bfs(int sx,int sy){
queue<node>q;
node t;
t.x=sx;t.y=sy;t.flag=0;
q.push(t);
vis[sx][sy][1]=0;
dis[sx][sy][1]=0;
while(!q.empty()){
node f=q.front();q.pop();
if(mp[f.x][f.y]=='G'&&f.flag==0&&vis[f.x][f.y][1]==0){//特判
dis[f.x][f.y][1]=dis[f.x][f.y][0]+1;
vis[f.x][f.y][1]=1;
f.flag=1;
q.push(f);
continue;
}
for(int i=0;i<4;i++){
node g;
int nowx=f.x+dx[i];
int nowy=f.y+dy[i];
g.x=nowx;g.y=nowy;
if(nowx<0||nowx>=n||nowy<0||nowy>=m||mp[nowx][nowy]=='#')
{
continue;
}
if(mp[nowx][nowy]=='G'){//状态情况考虑
if(vis[nowx][nowy][0]==0){
vis[nowx][nowy][0]=1;
dis[nowx][nowy][0]=dis[f.x][f.y][f.flag]+1;
g.flag=0;
q.push(g);
}
}
else if(mp[nowx][nowy]=='M'){
return dis[f.x][f.y][f.flag]+1;
}
else{
if(vis[nowx][nowy][1]==0){
vis[nowx][nowy][1]=1;
dis[nowx][nowy][1]=dis[f.x][f.y][f.flag]+1;
g.flag=1;
q.push(g);
}
}
}
}
return -1;
}
int main()
{
cin>>n>>m;
int sx,sy;
for(int i=0;i<n;i++){
cin>>mp[i];
for(int j=0;j<m;j++){
if(mp[i][j]=='@'){
sx=i;
sy=j;
}
}
}
int ret=bfs(sx,sy);
if(ret==-1){
cout<<"You can't save Mengxin";
}
else{
cout<<ret;
}
return 0;
}
完结！！！撒花！！！
