U5-5-BFS-2

原题链接：67324.4.0U5笔记合集

1943

2025-09-13 20:31:06

发布于：江苏

23阅读

0回复

0点赞

$一、课堂程序$

$T1 染色问题$

#include <bits/stdc++.h>
#include <queue>
using namespace std;
struct node {
	int x, y;
};
int mp[105][105];
int x, y, n, m, cr;
bool vis[105][105];
int dir[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};
queue<node> q;

void bfs()
{
	int cc = mp[x][y]; 	//cc: 连通块的颜色
	mp[x][y] = cr;		//染色第一个点
	//1.第一个搜索点入队
	q.push({x, y});
	//2.取出第一个搜索点
	while (q.size()) {
		node t = q.front();
		q.pop();
		for (int i=0; i<4; i++) {
			int a = t.x + dir[i][0];
			int b = t.y + dir[i][1];
			//越界 || 不是同一个联通块
			if (mp[a][b] == -1 || mp[a][b] != cc) continue;
			mp[a][b] = cr;
			q.push({a, b});
		}
	}
}

int main()
{
	memset(mp, -1, sizeof(mp));	//围成-1
	cin >> n >> m;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			cin >> mp[i][j];
	cin >> x >> y >> cr;
	if (cr == mp[x][y]) {
		for(int i=1; i<=n; i++) {
			for (int j=1; j<=m; j++) {
				cout<<mp[i][j] <<' ';
			}
			cout << endl;
		}
		return 0;
	}
	bfs();

	for(int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cout<<mp[i][j] <<' ';
		}
		cout << endl;
	}

	return 0;
}

$T2 岛屿问题$

#include <bits/stdc++.h>
using namespace std;
// 定义方向数组
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
// 定义地图数组用于储存
int MAP[102][102], n, m;
struct node {
	int x, y;
};

void bfs(int x, int y)
{
	// 定义队列并且将起始点压入队列
	queue<node> q;
	q.push({x, y});
	while (!q.empty()) {
		// 取出队头
		node now = q.front();
		q.pop();
		// 朝四个方向搜索
		for (int i = 0; i < 4; i++) {
			int fx = now.x + dx[i];
			int fy = now.y + dy[i];
			// 下一步的位置并未超出地图边界并且当前位置为1
			if (MAP[fx][fy] != 1) continue;
//			if (fx > 0 && fy > 0 && fx <= n && fy <= m && MAP[fx][fy] == 1) {
			// 将下一步位置压入队列并且将位置改变为0
			MAP[fx][fy] = 0;
			q.push({fx, fy});
		}
	}
}

int main()
{
	cin >> n >> m;
	// 输入地图
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> MAP[i][j];
		}
	}
	// 定义sum统计岛屿的数量
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			// 当前为岛屿的1，统计数量+1，并且将当前位置改为0
			if (MAP[i][j] == 1) {
				sum++;
				MAP[i][j] = 0;
				bfs(i, j);
			}
		}
	}
	// 输出统计的岛屿的数量
	cout << sum << endl;
	return 0;
}