YuriCode
0%

BFS

发表于 更新于 分类于
本文字数： 3.9k 阅读时长 ≈ 4 分钟

BFS

广度优先搜索算法（英语：Breadth-first search，缩写：BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表

迷宫

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;

const int N = 110;
int n, m;
int g[N][N];
int d[N][N];

void bfs() {
	queue<PII> q;
	q.push({0, 0});
	memset(d, -1, sizeof d);
	d[0][0] = 0;
	int dx[4] = {1, 0, -1, 0};
	int dy[4] = {0, 1, 0, -1};
	while (!q.empty()) {
		PII t = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int x = t.first + dx[i];
			int y = t.second + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
				d[x][y] = d[t.first][t.second] + 1;
				q.push({x, y});
			}  
		}
	}
	cout << d[n - 1][m - 1] << endl;
}

void solve() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> g[i][j];
		}
	}
	bfs();
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

Corn Maze S

https://www.luogu.com.cn/problem/P1825

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 333;
char g[N][N];
bool st[N][N];
int n, m;

struct Point{
	int x, y, d;
};

Point transmit(int x, int y, int d) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (g[i][j] == g[x][y] && (i != x || j != y)) {
				return {i, j, d};
			}
		}
	}
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs(int x, int y) {
	queue<Point> q;
	q.push({x, y, 0});
	while (!q.empty()) {
		auto f = q.front();
		q.pop();
		if (g[f.x][f.y] == '=') {
			cout << f.d << endl;
			return;
		}
		if (isalpha(g[f.x][f.y])) {
			f = transmit(f.x, f.y, f.d);
		}
		for (int i = 0; i < 4; i++) {
			x = dx[i] + f.x;
			y = dy[i] + f.y;
			if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] != '#' && !st[x][y]) {
				st[x][y] = true;
				q.push({x, y, f.d + 1});
			}
		}
	}
} 


void solve() {
	cin >> n >> m;
	int x, y;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> g[i][j];
			if (g[i][j] == '@') {
				x = i;
				y = j;
			}
		}
	}
	bfs(x, y);
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

Meteor Shower S

https://www.luogu.com.cn/problem/P2895

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

int dx[5] = {0, 1, 0, -1, 0};
int dy[5] = {0, 0, 1, 0, -1};

int n;

const int N = 333;

int times[N][N];
int st[N][N];

struct Point{
	int x, y, t;
};

void bfs() {
	queue<Point> q;
	q.push({0, 0, 0});
	st[0][0] = true;
	int ans = -1;
	while (!q.empty()) {
		auto f = q.front();
		q.pop();
		// 如果这个位置没有陨石
		if (times[f.x][f.y] == -1) {
			ans = f.t;
			cout << ans << endl;
			return;
		}
		// 如果在当前位置陨石已经坠落
		if (times[f.x][f.y] <= f.t) continue;
		for (int i = 1; i <= 4; i++) {
			for (int j = 1; j <= 4; j++) {
				int x = f.x + dx[i];
				int y = f.y + dy[i];
				if (x >= 0 && y >= 0 && !st[x][y]) {
					st[x][y] = true;
					q.push({x, y, f.t + 1});
				}
			}
		}
	}
	cout << ans << endl;
}

void solve() {
	cin >> n;
	// 初始化为 - 1
	memset(times, -1, sizeof times);
	for (int i = 0, a, b, t; i < n; i++) {
		cin >> a >> b >> t;
		// 将时间记录在陨石陨落的地方
		for (int i = 0; i < 5; i++) {
			int x = a + dx[i];
			int y = b + dy[i];
			// 输入陨石信息的时候，坠落时间并不是升序
			if (x >= 0 && y >= 0 && (times[x][y] == -1 || times[x][y] > t)) {
				times[x][y] = t;
			}
		}
 	}
	bfs();
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}