【BFS 广度优先搜索】入门教学
前言
本文主要讲解 BFS 是什么，以及最简单的模板题的题解。不讲非模板题，因为我不会。
想要让自己变成脑雾的了解 BFS 官方解释的可以前去阅读 OIwiki 的 BFS 讲解
1 模板介绍
BFS 思路：将有可能的情况（如在最短路题目中可以走的地点等）加入队列等待处理，在下一个 循环 / 递归 中处理。
适用于：求最短路的成本（距离/时间/花费）、找联通快
Q：为什么用队列？
A：队列先进先出，所以当你第一次到达终点的时候就肯定是最短的路线，可以用来找最短路。
2 最短路
个人认为最短路是 BFS 最常考的考法，可能是因为我做的少罢。
2.1 一维最短路
一维最短路例题 P1135 奇怪的电梯。
思路：
BFS 暴如力，将可以到达的层数加入队列 q，当当前层数是目标层数时，就找到了到达目标层数的最短路，这时候输出 top.step（目前的步数）就是正确答案。因为队列先进先出，所以当你第一次到达终点（目标层数）的时候就肯定是最短的路线。
如果把所有能去的层数都去了（q.size() == 0）还没到，那就到不了力！（悲）所以我们在到达的时候就把拿来判断是否达到过的 bool 变量 false，这样就可以在结束的时候通过判断 true 还是 false 来知道有没有到达目标层数。
呆马：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10;
struct lift
{
int sit/*当前层数*/, step/*多少步*/;
};
int n, a, b, k[N];
bool v[N], ans = true; // ans如果不初始化是false，这里需要把ans初始化为true
queue <lift> q;
void bfs(int x, int s)
{
q.push( {x, s} ); // 先将当前楼层（起点）加入队列
v[x] = true; // 表示起点已经到过了
while (q.size()) // 队列里有元素，代表还有可以到达的楼层
{
lift top = q.front(); // 设置一个top，这样就不用反复打q.front()了
q.pop(); // 直接弹出，因为到了就不再是可以到达的楼层了。
if (top.sit == b) // 判断是不是目标楼层
{
cout << top.step; // 是就直接输出top.step，即答案，因为队列的先进先出特性所以先到的肯定是最少步数。
ans = false; // 到达过目标楼层，ans变成false
return ; // 直接结束bfs以省下继续运行的时间，如果不写bfs函数写在主函数里可以break;
}
if ((top.sit + k[top.sit])/*当前楼层向上k[top.sit]层*/ <= n/*电梯有这层*/ and !v[top.sit + k[top.sit]]/*没到过*/) // 如果不判断到没到过会反复到同一楼层导致死循环
{
v[top.sit + k[top.sit]] = true; // 设为true以供下次判断到没到过
q.push( {top.sit + k[top.sit], top.step + 1} ); // 扔进队列，下个循环处理。
}
if ((top.sit - k[top.sit])/*当前楼层向下k[top.sit]层*/ >= 1/*电梯有这层*/ and !v[top.sit - k[top.sit]]/*没到过*/) // 因为可以向上和向下所以判断两次
{
v[top.sit - k[top.sit]] = true;
q.push( {top.sit - k[top.sit], top.step + 1} );
}
}
}
int main()
{
// 输入
cin >> n >> a >> b;
for (int i = 1; i <= n; i++)
cin >> k[i];
bfs(a, 0);
if (ans) // 如果没到达那ans就还是true，则代表没到达，会触发cout << -1。如果ans不是true而是false，就代表到过了，故不会触发。
cout << -1;
return 0; // 1145141919810
}2.2 二维最短路
二维最短路例题：P1825 [USACO11OPEN] Corn Maze S
思路
和一维最短路的差不多，像啊很像啊，只不过从
只不过里面的司马滑梯很恶心人，但是想到正解之后就明了了很多，这里就不放死法了。
滑梯的解决方法：用两个数组把每个滑梯的起点
贷蚂
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e2 + 10, INF = 0x3f3f3f3f;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1}; // 推荐这个dx[]和dy[]，这样就可以使用for循环快速枚举各个方向
struct sit // 地方坐标
{
int x, y, step;
};
struct tpsit // 传送门
{
int x, y;
};
int n, m, sx, sy, ex, ey, ans = INF;
char c, a[N][N];
bool v[N][N];
tpsit tps[N], tpe[N];
queue <sit> q;
void bfs(int sx, int sy)
{
q.push( {sx, sy, 0} );
while (q.size())
{
sit top = q.front();
q.pop();
if (top.x == ex and top.y == ey)
{
cout << top.step;
return ;
}
if (a[top.x][top.y] >= 'A' and a[top.x][top.y] <= 'Z')
{
char t = a[top.x][top.y];
if (top.x == tps[(int)t].x and top.y == tps[(int)t].y)
top.x = tpe[(int)t].x, top.y = tpe[(int)t].y;
else
top.x = tps[(int)t].x, top.y = tps[(int)t].y;
}
for (int k = 0; k < 4; k++) // 使用dx[]和dy[]快速枚举各个方向，注意是从0开始到3，因为下标从0开始
{
int xx = top.x + dx[k];
int yy = top.y + dy[k]; // xx和yy就是本次与top相邻的地方
if (xx >= 1 and xx <= n and yy >= 1 and yy <= m and v[xx][yy] /* xx和yy没出界且没到过 */)
{
v[xx][yy] = false;
q.push( {xx, yy, top.step + 1} );
}
}
}
}
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> c;
a[i][j] = c;
if (c == '@') // 起点
sx = i, sy = j, v[i][j] = false; // true能走，false不能走
else if (c == '=') // 终点
ex = i, ey = j, v[i][j] = true;
else if (c == '#') // 墙
v[i][j] = false;
else if (c == '.') // 路
v[i][j] = true;
else // 如果都不是就是传送门
{
v[i][j] = true;
if(tps[(int)c].x and tps[(int)c].y) // 如果已经有一个同样字母的传送门了
tpe[(int)c].x = i, tpe[(int)c].y = j; // 存入tpe
else // 之前没出现过，所以是第一个这种字母的传送门
tps[(int)c].x = i, tps[(int)c].y = j; // 存入tps
}
}
bfs(sx, sy); // bfs启动！
return 0;
}3 连通块
连通块经典例题：P1451 求细胞数量
思路
找到数字的时候直接开始 BFS!
BFS：把也是数字的地方的坐标塞进队列，并把它变成 0，这样就不会重复搜到了。一个 BFS 下来所有连通的是数字的地方就都变成 0 了，所以主函数中的 for 中找到了几次数字就有几个细胞。
好像说的不是很像人话。。。
直接看代码吧
逮玛
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
struct node
{
int x, y;
};
int n, m, a[N][N], ans;
bool v[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
queue <node> q;
bool check(int x, int y)
{
if (x >= 1 and x <= n and y >= 1 and y <= m and !v[x][y])
return true;
else
return false;
}
void bfs(int x, int y)
{
q.push( {x, y} );
v[x][y] = true;
while (q.size())
{
node top = q.front();
a[top.x][top.y] = 0; // 设为0，即把联通的全部设为0，这样就相当于慢慢把一个细胞吃掉（？。接下来就不会再在主函数中的for循环中找到同一个细胞了，因为被吃光了
v[top.x][top.y] = false;
q.pop();
for (int i = 0; i < 4; i++)
{
int xx = top.x + dx[i];
int yy = top.y + dy[i];
if (a[xx][yy] != 0 and !v[xx][yy])
{
q.push( {xx, yy} ); // 扔进队列q里面（成龙音
v[xx][yy] = true;
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
char c;
cin >> c;
a[i][j] = c - 48; // 对数字字符-48相当于-'0'，是一种便捷的将数字字符变成数字的方法
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (a[i][j] != 0) // 发现细胞（非0）
{
ans++; // 每发现一个不是0的都会被吃掉，所以一旦发现还有不是0的就说明是一个新的细胞
bfs(i, j); // 吃掉当前找到的细胞
memset(v, false, sizeof(v)); // 重置v数组
}
}
cout << ans;
return 0;
}4 后记
我是蒟蒻，只要是非模板的都不会（有些模板也不会。
既然如此只好开始怒切 BFS 水题了！！！
打注释不易，求赞🙏