1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int n, m; char g[1505][1505]; int cnt[100005]; //大小为i的星座,出现了几次 //把 (sx,sy) 对应的连通块大小返回,并把所有星星删掉 int dx[] = {0, 0, 1, -1, 1, 1, -1, -1}; int dy[] = {1, -1, 0, 0, 1, -1, 1, -1}; queue<pair<int, int>> q; int bfs(int sx, int sy) { int res = 1; q.push(make_pair(sx, sy)); while (!q.empty()) { pair<int, int> now = q.front(); q.pop(); for (int i = 0; i < 8; i++) { int nx = now.first + dx[i]; int ny = now.second + dy[i]; if (1 <= nx && nx <= n && 1 <= ny && ny <= m && g[nx][ny] == '*') { res++; g[nx][ny] = '.'; q.push(make_pair(nx, ny)); } } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> g[i][j]; //搜索 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (g[i][j] == '.') continue; //当前点是一个星星 g[i][j] = '.'; int now = bfs(i, j); //当前点对应的连通块大小 cnt[now]++; } //统计答案 int ans1 = 0; //星系数量 int ans2 = 0; //最大星系大小 for (int i = 1; i <= 100000; i++) { //所有大小为 i 的星座构成了一个星系 //大小为 i 的星座有 cnt[i] 个 //星系大小:i*cnt[i] if (cnt[i] > 0) { ans1++; ans2 = max(ans2, i * cnt[i]); } } cout << ans1 << " " << ans2 << endl; return 0; }
- 1
信息
- ID
- 1322
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 6
- 已通过
- 5
- 上传者