【BFS 广度优先搜索】入门教学

未分类
5.3k 词

前言

本文主要讲解 BFS 是什么，以及最最最简单的模板题的题解。不讲非模板题，因为我不会。

想要让自己变成脑雾的了解 BFS 官方解释的可以去阅读 OIwiki 的 BFS 讲解

1 模板介绍

BFS 思路：将有可能的情况（如在最短路题目中可以走的地点等）加入队列等待处理，在下一个 循环 / 递归 中处理。

适用于：求最短路的成本（距离/时间/花费）、找联通快

Q：为什么用队列？

A：队列先进先出，所以当你第一次到达终点的时候就肯定是最短的路线，可以用来找最短路。

2 最短路

个人认为最短路是 BFS 最常考的考法，可能是因为我做的少罢。

2.1 一维最短路

一维最短路例题 P1135 奇怪的电梯。

思路：

BFS 暴如力，将可以到达的层数加入队列 q，当当前层数是目标层数时，就找到了到达目标层数的最短路，这时候输出 top.step（目前的步数）就是正确答案。因为队列先进先出，所以当你第一次到达终点（目标层数）的时候就肯定是最短的路线。

如果把所有能去的层数都去了（q.size() == 0）还没到，那就到不了力！（悲）所以我们在到达的时候就把拿来判断是否达到过的 bool 变量 $ans$ 设为 false，这样就可以在结束的时候通过判断 $ans$ 是 true 还是 false 来知道有没有到达目标层数。

呆马：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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

思路

和一维最短路的差不多，像啊很像啊，只不过从 $sit$ 变成 $x$ 和 $y$。

只不过里面的司马滑梯很恶心人，但是想到正解之后就明了了很多，这里就不放死法了。

滑梯的解决方法：用两个数组把每个滑梯的起点 $x$ $y$ 和终点 $x$ $y$ 存下，然后等到达滑梯口的时候直接查询并传送就好了，如果滑梯有 CD 将会更恶心。

贷蚂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#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 中找到了几次数字就有几个细胞。

好像说的不是很像人话。。。

直接看代码吧

逮玛
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#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 水题了！！！