1 条题解

  • 0
    @ 2023-8-31 15:15:33
    #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
    上传者