NOIP入门组的一道题

今天给大家带来一道NOIP入门组的题。在看到这一题之后，我直呼好家伙：你管这叫入门组？！

题目描述：

Jimmy 和 Symbol 约好一起看星星，浩瀚的星空可视为一个长为 N、宽为 M 的矩阵，矩阵中共有 N×M 个位置，一个位置可以用坐标 (i,j)(i,j)（1≤i≤N，1≤j≤M）来表示。每个位置上可能是空的，也可能有一个星星。

对于一个位置 (i,j)(i,j)，与其相邻的位置有左边、左上、上面、右上、右边、右下、下面、左下 8 个位置。相邻位置上的星星被视为同一个星座，这种关系有传递性，例如若 (1,1),(1,2),(1,3)(1,1),(1,2),(1,3) 三个 位置上都有星星，那么这三个星星视为同一个星座。包含的星星数量相同的星座被视为一个星系（一个星系中的星座不一定相邻），星系的大小为星系中包含的所有星星数量。

由于 Symbol 太喜欢星系了，他就想考一考 Jimmy，让 Jimmy 求出星空中有多少个星系，他还想知道，最大的星系有多大。

代码（不一定是最佳，若有更好的代码欢迎提出）：

#include <iostream>
#include <map>
#include <vector>
using namespace std;
int n, m, cnt = 0;
char star[1502][1502];
int a[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int b[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

void f(int x, int y) {
    star[x][y] = '.';
    cnt++;
    for (int i = 0; i < 8; ++i) {
        int xx = x+a[i];
        int yy = y+b[i];
        if (xx >= 0 && xx < n && yy >= 0 && yy < m) {
            if (star[xx][yy] == '*') {
                f(xx, yy);
            }
        }
    }
}
int main() {
    map<int, int> s;
    int max = 0;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> star[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cnt = 0;
            if (star[i][j] == '*') {
                f(i, j);
                s[cnt]++;
            }
        }
    }
    for (pair<int, int> i : s) {
        if (max < i.first * i.second) {
            max = i.first * i.second;
        }
    }
    cout << s.size() << ' ' << max;
    return 0;
}

实例：

输入：

5 7
*......
..**..*
.*...*.
...*...
....*..

输出：

3 4

作者信息：2011年12月21日生于福建省厦门市