快速理解宽度优先搜索并用c++实现
1，广度优先搜索
q：什么是广度优先搜索？
a：我们以走迷宫为例：
迷宫问题
一个迷宫
00010
01000
00100
11010
01110
其中1为障碍，0为无障碍，入口为（1,1），出口为（m,n),每次移动只能从一个无障碍单元移动到其周围4个方向的另外一个无障碍单元
输入：第一行为两个整数，m，n，保证1<m,n<100
以下m行，每行n个整数
表示n行m列的0-1矩阵
输出：输出路径坐标，如果没有路，输出-1
【输入样例】
1 2
0 0
【输出样例】
1 1
1 2
利用队列的特点，一层一层向外寻找拓展可以走的点，直到找到出口为止 （当然，这里的队列也可以用其他东西代替）
q：具体实现方法？
a：假设当前位置是（x，y），为了避免回头重新搜索上一步，我们将上一步位置设为-1，这样就可以保证不会回头。
紧接着，当我们到达目的地的时候，理论上就会找到“最快”的路径了 。
另外，我们需要用两个一维数组来实现存储各个方向的取值 ，可以参考下面代码
q：我还是看不懂怎么办？
a：举个例子吧
比如地图
000
101
010
第一步：我们在左上角1,1位置
第二步：存在两种走法：1,2和2,2
第三步，存在3种走法（不走已经走过的地方）：1,3、3,3和3,1
此时，由于3,3满足题设，所以得到了最短路径1,1。2,2。3,3。
事实上，当我们实现的时候，往往是倒着来的：3,3的上一步是2,2.而2,2的上一步是1,1
具体代码
注：该代码输出结果为倒序
注2：该代码所有的具体解释请下移
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define N 1000
int m,n;
struct Map
{
int x;
int y;
}
pre[N][N];
bool vist[N][N];
int map[N][N];
int a[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
bool in(int x,int y)
{
if(x<0||x>m||y<0||y>n)return false;
return true;
}
void bfs()
{
queue<Map>q;
while(!q.empty())q.pop();
vist[0][0]=true;
Map cu;
cu.x=0;
cu.y=0;
q.push(cu);
while(!q.empty())
{
cu=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=a[i][0]+cu.x;
int y=a[i][1]+cu.y;
if(in(x,y) && !vist[x][y] && !map[x][y])
{
Map temp;
vist[x][y]=true;
temp.x=x;
temp.y=y;
q.push(temp);
pre[x][y].x=cu.x;
pre[x][y].y=cu.y;
}
}
}
}
void PrintWay(int x,int y)
{
if(x==0 && y==0)
{
printf("%d %d\n",x+1,y+1);
return;
}
printf("%d %d\n",x+1,y+1);
PrintWay(pre[x][y].x,pre[x][y].y);
}
int main()
{
cin >> m >> n;
for(int i=0;i<m;i++)
{
getchar();
for(int j=0;j<n;j++)
{
char a;
a=getchar();
map[i][j]=(int)a -48;
}
}
memset(vist,false,sizeof(vist));
bfs();
PrintWay(m-1,n-1);
return 0;
}
对于代码的具体解释
1，前设
struct Map
{
int x;
int y;
}
pre[N][N];
bool vist[N][N];
int map[N][N];
int a[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
Map结构：用来记录x，y坐标
这里我们设置了三个表，第一个pre，代表的是记录，记录该位置之前应该在什么位置，比如1,2的上一步在1,1 ，那么
pre[1][2].x = 1;
pre[1][2].y = 1;
这样的话，我们就可以根据“终点”得到它“上一步”所在的位置，然后不停上一步，最终得到一条反向的路了。（你只要把终点和起点变化一下，就可以获得正向的路了）
紧接着，vist用来储存的是“这条路是否被走过”，如果被走过，则为true，否则为false。目的是为了防止我们在一个地方绕一辈子圈圈。
最后，map用来储存地图情况，1是障碍，0是路。
2，确认是否脱离边界
bool in(int x,int y)
{
if(x<0||x>m||y<0||y>n)return false;
return true;
}
我们每走一步，都要首先确定一件事情：我是不是跑出地图外面了，因此在这里要设置一个判断脱离边界的函数
3，队列
队列是一种特殊的线性表，只允许在前端删除，后端插入。
进行插入操作的叫做队尾，删除的叫做队头。队列没有元素的时候，称为空队列。往队列中加入元素叫做入队，删除元素叫做出队
声明方式 queue<数据类型>名称; 见上，这里的Map是我们之前设置的用来记录坐标的xy
基本方法：
q.push(x);入队，将x接到队列末端
q.pop();出队，将队列第一个元素删除。
q.front();访问队头元素
q.back(); 访问队尾元素
q.empty();判断队列是否为空，是的话返回true
q.size();获得队列中元素个数
4，bfs函数（广度搜索函数）
第一部分：
首先清零我们刚刚设置的队列，并且在队列内加入第一个坐标：（0,0），并且将判断已走过的vist的0,0坐标改为true（来表示它已经被走过了）
while(!q.empty())q.pop();
vist[0][0]=true;
Map cu;
cu.x=0;
cu.y=0;
q.push(cu);
第二部分：
将队列内的数据提取出来进行运算
while(!q.empty())
{
cu=q.front();
q.pop();
接上一步，我们将队列里的第一个数的数据提取出来到cu，并且删除这个数据（现在队列中就为空了）。这样的话，我们才可以对这个数据进行检测和运算
第三部分
for(int i=0;i<4;i++)
{
int x=a[i][0]+cu.x;
int y=a[i][1]+cu.y;
if(in(x,y) && !vist[x][y] && !map[x][y])
{
Map temp;
vist[x][y]=true;
temp.x=x;
temp.y=y;
q.push(temp);
pre[x][y].x=cu.x;
pre[x][y].y=cu.y;
}
}
我们判断向每一个方向前进，所以循环四次，分别尝试向四个方向前进。
如果出现：
1，不超出边界（ in(x,y) ）
2，路没走过（ !vist[x][y] ）
3，路可以走（ !map[x][y] )
那么我们就执行我们的内容：将“下一步的上一步”设置为“这一步”的坐标
简单来说，就是我们从（1,1）走到（1,2），就将（1,2）的上一步设为（1,1）
这样，我们的pre组中，每一步的上一步就都有了。
4，递归输出
在已经知道每一步的上一步后，我们就可以通过递归来从终点找到回到起点的路了。
我们只要创建一个简单的递归，就可以完成这个目的：
void PrintWay(int x,int y)
{
if(x==0 && y==0)//递归出口
{
printf("%d %d\n",x+1,y+1);
return;
}
printf("%d %d\n",x+1,y+1);
PrintWay(pre[x][y].x,pre[x][y].y);
}
不懂递归请自行百度。
5，主函数，输入内容，输出结果
最简单的一步，将你的所做的一切穿起来
int main()
{
cin >> m >> n;
for(int i=0;i<m;i++)
{
getchar();//用来储存回车键防止影响正常输入
for(int j=0;j<n;j++)//创建一个循环，将整个地图录入map中
{
char a;
a=getchar();//这里使用getchar的原因是我们每次只录入一个字符
map[i][j]=(int)a -48;
}
}
memset(vist,false,sizeof(vist));//把vist全部化为false,意思是开始的时候哪里都没走过
bfs();//搜索！
PrintWay(m-1,n-1);//打印结果
return 0;
}
![swmm与lisflood-fp源码如何一起编译 CMake命令[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)