U5-5-BFS-2
原题链接：67324.4.0U5笔记合集
2025-09-13 15:34:43
发布于：江苏
22阅读
0回复
0点赞
染色问题
#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;
}
/*
[【广度优先搜索(二)】图像渲染]
题目描述
有一幅 n×m 的图画，给你一个需要上色的点 [x,y] 和颜色 a。
从给出的上色点开始上色，为了完成上色工作，
从初始位置开始，将所有与上色点有连接的点全部涂上相同的颜色，
最后输出经过上色后的图像。
提示
数据范围：1≤n,m≤50, 1≤x≤n,1≤y≤m,1≤a≤9
样例说明：
当前从 [1,1] 点出发将所有和 [1,1] 点相连接并且颜色相同的块全部修改为指定颜色，
与 [1,1] 点连接的有 [1,2],[1,3],[2,1],[2,2],[3,1].
输入格式
第一行输入一个 n,m,表示有 n 行 m 列
接下来输入 n 行每一行有 m 个点
接着给出需要上色的点[x,y] 和颜色 a
输出格式
输出经过上色后的图像
样例组
输入#1
3 3
1 1 1
1 1 0
1 0 1
1 1 2
输出#1
2 2 2
2 2 0
2 0 1
*/
岛屿问题
#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;
}
这里空空如也
有帮助，赞一个