算法
可以从任意还未搜索过的星星*
开始搜索。
这里采用深搜的方式,搜索出每个星座。对于每个星座,要分配给合适的星系,再取最大的星系输出。
注意:星系的大小=星座数*星座大小。
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1510, MAXS = 1e5 + 10;
int n, m, a[MAXN][MAXN], cnt, s[MAXS];// s[i]表示星星数量为i的星座
int d[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
bool vis[MAXN][MAXN];
int res1, res2; // res1:有多少星系 res2:最大的星系有多大
void dfs(int x, int y) {
cnt++;
vis[x][y] = 1;
for (int i = 0; i < 8; ++i) {
if (!vis[x + d[i][0]][y + d[i][1]] && a[x + d[i][0]][y + d[i][1]]) {
dfs(x + d[i][0], y + d[i][1]);
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
char c[MAXN];
scanf("%s", c + 1);
for (int j = 1; j <= m; ++j) {
if (c[j] == '.') a[i][j] = 0;
else a[i][j] = 1;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (!vis[i][j] && a[i][j]) {
cnt = 0;
dfs(i, j);
s[cnt]++;
}
}
}
for (int i = 1; i < MAXS; ++i) {
if (s[i]) {
res1++;
res2 = max(res2, i * s[i]);
}
}
cout << res1 << ' ' << res2 << '\n';
return 0;
}
大佬能解释一下样例吗,我没看懂。。。
只讲第一个样例:
有1星星座,2个2星星座,1个3星星座
星座大小相同视作同一个星系,所以有3个星系,另外最大星系由2个2星星座构成,所以大小是4
看懂了,当时太急没看到有星系星座星星这三个类别,谢谢大佬了