NOIOnline #3 第二题 观星 P6566
  • 板块灌水区
  • 楼主码农同志
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/5/24 19:47
  • 上次更新2023/11/7 01:47:41
查看原帖
NOIOnline #3 第二题 观星 P6566
268200
码农同志楼主2020/5/24 19:47

码风奇怪的小白,勿喷哦

so有没有大神能帮我看看观星这题我错了没有?

民间数据没出来,没办法测QWQ

不多说(说了很多)上代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#define N 1510
#define M 100010

using namespace std;

int n, m;
int s[M];
vector<vector<char> > a(N, vector<char>(N));
    void dfs(vector<vector<char> >& grid, int r, int c, int& a) {
        int nr = n;
        int nc = m;

        grid[r][c] = '.';
        if (r - 1 >= 0 && grid[r-1][c] == '*') {++a;dfs(grid, r - 1, c, a);}
        if (r + 1 < nr && grid[r+1][c] == '*') {++a;dfs(grid, r + 1, c, a);}
        if (c - 1 >= 0 && grid[r][c-1] == '*') {++a;dfs(grid, r, c - 1, a);}
        if (c + 1 < nc && grid[r][c+1] == '*') {++a;dfs(grid, r, c + 1, a);}
        if (c + 1 < nc && r-1>=0 && grid[r-1][c+1] == '*') {++a;dfs(grid, r-1, c + 1, a);}
        if (c + 1 < nc && r+1<nr && grid[r+1][c+1] == '*') {++a;dfs(grid, r+1, c + 1,a);}
        if (c - 1 >= 0 && r-1>=0 && grid[r-1][c-1] == '*') {++a;dfs(grid, r-1, c - 1,a);}
        if (c - 1 >= 0 && r+1<nr && grid[r+1][c-1] == '*') {++a;dfs(grid, r+1, c - 1,a);}
    }

    void numIslands(vector<vector<char> >& grid, int& a) {
        int nr = n;
        if (!nr) return;
        int nc = m;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '*') {
                    a = 1;
                    dfs(grid, r, c, a);
                    s[a]++;
                }
            }
        }
    }
int main(){
	freopen("star.in","r",stdin);
	freopen("star.out","w",stdout);
    cin >> n >> m;
    int i, j;
    for(i = 0; i < n; ++i){
        for(j = 0; j < m; ++j){
            cin >> a[i][j];
        }
    }
    int res = 0;
    numIslands(a, res);
    int count = 0, maxa = 0;
    for(i = 0; i < M; ++i){
        if(s[i] != 0){
            count++;
            if(maxa < i*s[i]){
                maxa = i*s[i];
            }
        }
    }
    fclose(stdin);
    fclose(stdin);
    cout << count << ' ' << maxa;
    return 0;
}
2020/5/24 19:47
加载中...