111
2025-03-01 20:12:20
发布于：四川
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt = 0, w;
int ans = 0;
char a[1510][1510]; // 用来存星空
int Stars[100010], book[1510][1510];
struct node {
int x, y; // BFS 的结构体，所在第几行，第几列
} temp;
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
int bfs(int p0, int q0) { // 找到的这一颗星星的坐标是(p0,q0)
queue<node> q;
q.push({p0, q0});
book[p0][q0] = 1;
int Size_ = 0;
while (q.size()) {
Size_; // 星座的大小加一
temp = q.front();
q.pop();
for (int i = 0; i < 8; i) {
int fx = temp.x + dx[i];
int fy = temp.y + dy[i];
if (fx >= 1 && fx <= n && fy >= 1 && fy <= m &&
a[fx][fy] == '' && book[fx][fy] == 0) {
book[fx][fy] = 1;
q.push({fx, fy});
}
}
}
return Size_; // 返回星座大小
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> a[i][j];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == '' && book[i][j] == 0) {
w = bfs(i, j);
Stars[w];
}
}
}
for (int i = 1; i <= 100000; i) {
if (Stars[i] != 0) {
cnt++;
ans = max(ans, (i * Stars[i]));
}
}
cout << cnt << " " << ans << endl;
return 0;
}
这里空空如也
有帮助，赞一个