U5-6-BFS-3
原题链接：67324.4.0U5笔记合集
2025-09-20 17:04:29
发布于：江苏
42阅读
0回复
0点赞
T2 观星
#include <bits/stdc++.h>
using namespace std;
const int N = 1510;
int n, m, cnt, ans, bucket[100010]; //统计星系
char mp[N][N];
struct node {
int x, y;
};
int vis[N][N];
int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};
int bfs(int x, int y)
{
queue<node> q;
q.push({x, y});
vis[x][y] = 1;
int ret = 0; //星座的大小
while (q.size()) {
ret++;
node t = q.front();
q.pop();
for (int i=0; i<8; i++) {
int a = t.x + dx[i], b = t.y + dy[i];
if (a>0&&a<=n&&b>0&&b<=m&&mp[a][b]=='*'&&vis[a][b]==0) {
vis[a][b] = 1;
q.push({a, b});
}
}
}
return ret;
}
int main()
{
cin >> n >> m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cin >> mp[i][j];
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
if (mp[i][j] == '*' && vis[i][j]==0)
bucket[bfs(i, j)] ++; //数量相同的是属于同一个星座
}
}
//统计答案
for (int i=1; i<=100000; i++) {
if (bucket[i]) {
cnt++;
ans = max(ans, i*bucket[i]); //星的数量 * 星座的个数
}
}
cout << cnt << ' ' << ans << endl;
return 0;
}
T1. 二进制矩阵中的最短路
#include <bits/stdc++.h>
using namespace std;
int n;
// 创建地图数组和标记是否用过的数组
int grid[1004][1003];
int dist[1004][1003]; //dis
// 定义方向数组和结构体储存当前位置
int dx[8] = {1, -1, 0, 0,1,1,-1,-1};
int dy[8] = {0, 0, 1, -1,1,-1,1,-1};
struct node {
int x, y;
};
int bfs()
{
// 定义队列并将起始点压入队列，并且标记已用过
queue<node> q;
q.push({1, 1});
dist[1][1] = 1; //到达第一个点是 1
while (!q.empty()) {
node now = q.front();
q.pop();
// 到达最终位置，输出到达最终位置的路径长度
if (now.x == n && now.y == n) {
return dist[now.x][now.y];
}
for (int i = 0; i < 8; i++) {
int fx = dx[i] + now.x;
int fy = dy[i] + now.y;
// 下一个行走的位置超出边界则跳过
if (fx < 1 || fx > n || fy < 1 || fy > n) {
continue;
}
// 单元格值不为 0 或已被访问则跳过
if (grid[fx][fy] == 1 || dist[fx][fy] <= dist[now.x][now.y] + 1) {
continue;
}
// 路径长度+1并将下一个位置压入
dist[fx][fy] = dist[now.x][now.y] + 1;
q.push({fx, fy});
}
}
// 如果不存在路径返回-1输出
return -1;
}
int main()
{
cin >> n;
// 将当前的图存入数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> grid[i][j];
}
}
// 如果起始位置为1，那么输出-1
if (grid[1][1] == 1) {
cout << "-1" << endl;
return 0;
}
// 对dist数组做初始化操作
memset(dist, 0x3f, sizeof dist);
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// dist[i][j] = 9999;
// }
// }
cout << bfs() << endl;
return 0;
}
T1 填图颜色
#include <bits/stdc++.h>
using namespace std;
int n,vis[40][40];
int dirx[4]= {-1,1,0,0},diry[4]= {0,0,-1,1};
struct node {
int x,y;
};
bool check(node w)
{
if(w.x>=0 && w.x<=n+1 && w.y>=0 && w.y<=n+1) {
if(vis[w.x][w.y]==0) {
return 1;
}
}
return 0;
}
void bfs(int sx, int sy)
{
queue<node> q;
q.push({sx,sy});
vis[sx][sy]=-1;
while(q.size()) {
node r=q.front();
q.pop();
for(int i=0; i<4; i++) {
node l;
l.x=r.x+dirx[i];
l.y=r.y+diry[i];
if(check(l)) {
q.push(l);
vis[l.x][l.y] = -1;
}
}
}
}
int main()
{
cin>>n;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
cin>>vis[i][j];
}
}
bfs(0,0);
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(vis[i][j]==-1) cout<<0<<' ';
if(vis[i][j]==0) cout<<2<<' ';
if(vis[i][j]==1) cout<<1<<' ';
}
cout<<endl;
}
return 0;
}
T2. 被包围的区域
#include <bits/stdc++.h>
using namespace std;
struct node{
int x, y;
};
int n, m;
// 定义地图和方向数组
char mp[105][105];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main() {
// 输入地图大小和地图
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mp[i][j];
}
}
// 定义队列将地图四周为O的全部存入队列，并且将其改为A
queue<node> que;
for (int i = 0; i < n; i++) {
if (mp[i][0] == 'O') {//第一列
que.push({i, 0});
mp[i][0] = 'A';
}
if (mp[i][m - 1] == 'O') {//最后一列
que.push({i, m-1});
mp[i][m - 1] = 'A';
}
}
for (int i = 1; i < m - 1; i++) {//第一行
if (mp[0][i] == 'O') {
que.push({0, i});
mp[0][i] = 'A';
}
if (mp[n - 1][i] == 'O') {//最后一行
que.push({n - 1, i});
mp[n - 1][i] = 'A';
}
}
// 所有与当前位置相连的O都是暴露在外的
while (!que.empty()) {
node t = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
int mx = t.x + dx[i], my = t.y + dy[i];
// 如果没超出范围并且当前位置不是O那么则跳过
if (mx < 0 || my < 0 || mx >= n || my >= m || mp[mx][my] != 'O') {
continue;
}
// 如果为O将当前位置压入队列并且改为A
que.push({mx, my});
mp[mx][my] = 'A';
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 将所有的A标记都改为O
if (mp[i][j] == 'A') {
mp[i][j] = 'O';
}
// 如果是O标记那么说明当前这个位置之前是被包含的，需要改为X
else if (mp[i][j] == 'O') {
mp[i][j] = 'X';
}
}
}
// 最后输出地图
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << mp[i][j];
}
cout << endl;
}
return 0;
}
/*
【广度优先搜索(二)】被围绕的区域]
题目描述
给你一个 m?n 的矩阵，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，
并将这些区域里所有的 'O' 用 'X' 填充
提示
数据范围：
1<=m,n<=200
样例说明：
被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。
任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。
如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
输入格式
第一个给出两个整数 M 和 N.
接着给出一个 m?n 的矩阵
输出格式
输出改变后的矩阵
样例组
输入#1
4 4
XXXX
XOOX
XXOX
XOXX
输出#1
XXXX
XXXX
XXXX
XOXX
*/
这里空空如也
有帮助，赞一个