关于广度优先搜索算法(BFS)题目的套路小结

关于广度优先搜索算法(BFS)题目的套路小结

　　这两天查了很多广度优先搜索算法，看到了很多文章，感觉里面对于这种模板的讲解不够细致。首先，广度优先算法的核心是它一定是把同一级的子节点都拉入队列，之后才会去遍历下一级节点。关于此算法的详细内容请自行查阅相关资料，本篇博客将集中在具体应用上。
　　使用限定条件:最典型的是走迷宫，但说白了其实是题目要求我们探寻最短路径，或者说题目可以被简化成坐标按几种种步长移动(不局限于二维,也可能是一维），也不局限于寻路，也可以用于对某一特定条件节点的搜索，或是对这种特定坐标进行标记。但都有一个核心点，就是要连续搜索，在找到一个合法节点后需要去探知其附近的合法节点，直到这一个区域内符合合法节点的节点都被找到。
　　注：以下所说的父子节点，从a坐标移动到b坐标,a节点就是父节点,b节点就是a的子节点

一.模板

本篇先以一道题的题解来说明问题模板可以大体分成6部分
1.头文件段
2.坐标结构体段
3.障碍物预设段
4.已访问结点和移动坐标段
5.BFS算法函数段
6.主函数段定义一个二维数组： int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)1.头文件段
//这里使用c++的<queue>函数，这样可以快速进行队列的操作，没啥好解释的，背下
#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
#include<queue>2.坐标结构体段
//记录结点坐标，特别注意，这里的坐标也可能是一维的，不要死板，具体情况具体分析。
struct mi{int x;int y;
}ca;3.障碍物预设段（有可能没有，是无障碍题目）
//这里往往是初始化好的迷宫地图，或是什么其他条件的障碍物,在这里1就是障碍物,
这个地图要么是自己输入，要么是题目已知条件
int map[5][5];={{0,1,0,0,0},{0,1,0,1,0},{0,0,0,0,0},{0,1,1,1,0},{0,0,0,1,0},}   
struct mi zhen[5][5];  //这里记录着路径子节点与父节点的对应关系在5中详解4.已访问结点和移动坐标段
//注意移动坐标要一一对应，可以使用二维数组，代表着在迷宫中怎样移动
int visited[5][5];     //用来记录已访问节点，但是也可以不要这个数组，每次走到后直接改变图，
把此节点的内容直接变成障碍物即可
int xx[4]={1,-1,0,0};
int yy[4]={0,0,-1,1};5.BFS算法函数段
//这里主要是对BFS算法的套用,具体可以看下列详细注释
注意：凡是写到背下的，说明其基本可以完全复用，而且处于此模板的核心部分void BFS()
{memset(visited,0,sizeof(visited));       //背下，初始化已访问数组queue<mi>q;                              //背下,初始化队列struct mi A;                             //背下，把第一个结点压入队列里A.x=0;                                   //初始化第一个节点坐标 没啥好说的A.y=0;                                                                                        visited[0][0]=1;                         //初始化首已访问节点，说明自己已被访问zhen[0][0].x=0;                          //初始化对应关系底层结点  下面将详细解释zhen[0][0].y=0;//特别注意:千万不要死板，此题是走迷宫，所以首节点是左上角，其他题可不一定，千万不要一堆0就上去了q.push(A);                              //将首节点压入队列                 while(!q.empty())                       //背下，只要队列里还有东西就继续{struct mi te=q.front();             //这两句背下q.pop();if(te.x==4&&te.y==4)                //找到答案后退出 return;//特别注意:不一定都需要退出条件，如果题目要求我们对单节点进行移动（后面会提到）for(int i=0;i<4;i++)                //背下，把各个方向都试着走一遍{int zx=te.x+xx[i];              //zx,zy为移动后节点坐标int zy=te.y+yy[i];if(zx<0||zx>4||zy<0||zy>4||map[zx][zy]||visited[zx][zy])      //背下，判断是否为合法路径，比如墙和已走过节点都为非法路径，但让我前面提到过，可以把已走过节点直接在地图上变成墙也行，这样就不需要visited数组continue;visited[zx][zy]=1;              //将已访问节点标志为1  下标对应当前节点struct mi kao;                  //背下，将合法子节点压入队列kao.x=zx;kao.y=zy;q.push(kao);//记录着谁走到了它zhen[zx][zy].x=te.x;           //现在来说明这个二维数组怎样记录最短路径，首先这个数组里存的是坐标结构体，数组下标代表着子节点坐标，而数组内容存着父节点坐标，这样皆可以通过循环，一级一级找上去，既可以知道最短路径长度，也可以打印所有经过的节点坐标zhen[zx][zy].y=te.y;}}          
}6.主函数部分
//略写 这没什么好说的 根据题目要求不同这个地方的灵活性也最大
int main(void)                   
{for(int m=0;m<5;m++)                  //初始化迷宫地图{for(int n=0;n<5;n++){scanf("%d",&map[m][n]);}}BFS();            int num[30][2];int x=4,y=4;int i=0;while(1){                                //把父子节点关系倒着取出放入数组中以便打印int k;k=x;x=zhen[x][y].x;y=zhen[k][y].y;num[i][0]=x;num[i][1]=y;  i++;if(x==0&&y==0)break;}for(int j=i-1;j>=0;j--){printf("(%d, %d)n",num[j][0],num[j][1]);          //打印路径节点部分}printf("(4, 4)");     return 0;
}

　　看完这个题你可能已经了解到了这个套路的框架是什么，那么下面我将用两道题展示怎么分析，怎么套，不过这次的注释不会很详细
　
二.例题2详解部分　
1.分析

   在某知名游戏中,“闪现”是一个很有用的技能,某天你在机缘巧合之下在现实生活中也学会了这个技能,
你目前处在坐标为 a的位置上,欲到坐标为 b 的地方去。你在 1 秒钟内可以移动 1 个单位的距离,
当然也可以使用“闪现”使你目前的坐标翻倍。
输入输入的数据有多组,每组数据包含两个以空格为分隔符的非负整数 a 和 b。其中,0 ≤ a ≤ 100000 且 0 ≤ b ≤100000。
输出输出你由 a 出发到达坐标 b 所需的最短时间,每组数据的输出占一行。
样例输入
5 17
10 20
样例输出
4
1分析过程:首先确定我们能不能使用此模板，一看题有一个目标坐标b,很好，再一看，需要移动坐标后再次移动，
连续移动，找到目标位置，还是属于寻路,这就非常好，已经基本确定可以使用此模板。此时不要急，先尝试简化
题目，进一步看一看题目是否符合。简化后题目应该是这样子，坐标轴为一维，坐标轴长度100000，你在坐标为a的点上，现在你一次有三种移动
方法，翻倍移动，前进一步或后退一步，问怎样连续移动后到达b点的时间最短。你这样简化后应该都笑了，因为这不就是简化版的迷宫吗？还是一维的，还只有三种移动方向，还是无障碍
地图，还问的是你最短时间（此题移动一次算一秒，故相当于问你最短移动次数）,现在可以直接套了。

2.解题

#include<iostream>
using namespace std;#include<stdio.h>
#include<string.h>
#include<queue>struct mi{int x;
}ca;void BFS(int a,int b,struct mi *zhen)
{int zx;int visited[100005];int xx[3]={0,1,-1};memset(visited,0,sizeof(visited));queue<mi>q;struct mi A;A.x=a;visited[a]=1;zhen[a].x=a;q.push(A);while(!q.empty()){struct mi te=q.front();q.pop();if(te.x==b)return;for(int i=0;i<3;i++)  //让它走3种情况{if(i==0)zx=te.x+te.x;elsezx=te.x+xx[i];if(zx<0||zx>100000||visited[zx])continue;visited[zx]=1;struct mi kao;kao.x=zx;q.push(kao);zhen[zx].x=te.x;}}
}int main(void)
{int a,b;while(scanf("%d%d",&a,&b)!=EOF){ struct mi zhen[100005]; BFS(a,b,zhen);int x=b;int i=0;while(x!=a){x=zhen[x].x;i++;}printf("%dn",i);}return 0;
}//这几乎和迷宫的代码完全一致，把二维改成一维即可

三.例题3详解部分
1.分析

　　你刚刚承包了一块大小为 M * N 的油田,并通过专业器具知道了哪些区块下面蕴藏着石油。
现在你想知道至少需要多少台机器才能将这块油田的所有石油采完。如果蕴藏着石油的区域如果互相
连接,那么这两块区域可以使用同一台机器。例如:若 M = 1, N = 5,其中(1, 1), (1, 2)和
(1, 4)区域有石油,那么由于(1, 1)和(1, 2)这两块区域连在一起,所以只需要两台机器即可
采完所有石油。
输入输入的数据有多组,每组数据首先是两个正整数 M 和 N,接下来是一个 M 行N 列的矩阵,
矩阵表示油田,矩阵中有两种可能的值,一种是“*”,表示此处没有油,一种是“@”,代表此处蕴藏
着石油。若 M, N 均为 0,则表示输入结束,该组数据 不输出任何内容 。
输出对于每组数据,在一行内输出需要机器的数量。
样例输入
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
样例输出
0
1
2
2分析过程:首先看到题目里有预设障碍物，而且需要搜索一个节点附近的所有合法节点，而且是属于连续
搜索，需要把每个找到的合法节点的每个方向都搜索一遍，不需要最短路径，没有目标。将所有节点搜索完成
退出。这样一看只能说应该可以用。我们再简化一下看看。简化题目后，应该是对于地图内的一个节点，只要与它相邻（包括斜相邻）的坐标上有合法节点，这就算
连通，也就是说只要是互相连通的节点，整个连通区域只需要一个机器，你需要找到有多少个这样的区域。那么怎么用呢，我们思考，它这个题的意思相当于需要我们去遍历整个地图，在每一个合法节点的周围探
知其附近有没有合法节点，并且要连续搜索，直到把搜索出的每一个合法节点的八个方向全部搜索完为止，并
且在搜索到合法节点后，将此节点的图型改成非法，以避免重复。那么就符合了我们此套路的核心--连续搜索，标记。

2.解题

#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
#include<queue>struct mi{int x;int y;
}ca;//初始障碍
char **map;int xx[8]={1,-1,0,0,1,1,-1,-1};        //移动方向
int yy[8]={0,0,-1,1,1,-1,1,-1};int BFS(int a,int b,int ca,int ka)
{if(map[a][b]=='*')                 //初始节点是非法节点不搜索return 0;queue<mi>q;struct mi A;A.x=a;A.y=b;q.push(A);while(!q.empty()){struct mi te=q.front();q.pop();for(int i=0;i<8;i++)  {int zx=te.x+xx[i];int zy=te.y+yy[i];if(zx<0||zx>=ca||zy<0||zy>=ka||map[zx][zy]=='*')continue;map[zx][zy]='*';          //将合法节点改为非法节点struct mi  kao;kao.x=zx;kao.y=zy;q.push(kao); }}return 1;                         //说明此初始节点属于连通区域
} int main(void)
{int a,b,k,m,key,daan;while(1){ daan=0;scanf("%d%d",&a,&b);getchar();if(a==0&b==0)break;map=(char**)malloc(a*sizeof(char*));for(m=0;m<a;m++)map[m]=(char *)malloc(b*sizeof(char));for(int m=0;m<a;m++){for(int n=0;n<b;n++){map[m][n]=getchar();}getchar();             }for(int i=0;i<a;i++)          //遍历整个地图{for(int j=0;j<b;j++){key=BFS(i,j,a,b);if(key==1){daan++;}}}printf("%dn",daan);for(int g=0;g<a;g++){            free(map[g]);}free(map);}return 0;
}//也没有什么特别大的改动，基本还是那个框架，只不过不需要记录路径移动坐标和长度，此题只用了搜索和标记

四.总结
　　通过对以上三道算法题的探究，想必你已经初步了解到了这种模板的适用性是比较广泛的，
核心是搜索与标记，希望你能多找相关类型的的题目进行练习，算法题对于逻辑思维较差者确实
比较困难，合理记忆模板将有效帮助你解决问题。