1 solutions
-
0
#include<bits/stdc++.h> using namespace std; int n,m; const int N=1510; const int M=100010; bool st[N][N];//标记是否走过 char g[N][N]; //地图 int cnt[M]; //每个星系的数目 int dx[]={-1,-1,-1,0,0,1,1,1}; //周围的方向 int dy[]={-1,0,1,-1,1,-1,0,1}; typedef pair<int,int> PII; #define x first #define y second int bfs(int x,int y) //宽度优先搜索 { queue<PII> q; int res=1; q.push({x,y}); while(q.size()) { auto t=q.front(); q.pop(); for(int i=0;i<8;i++) { int a=t.x+dx[i],b=t.y+dy[i]; if(a<1||a>n||b<1||b>m) continue; if(g[a][b]=='.') continue; if(st[a][b]==1) continue; res++; st[a][b]=1; q.push({a,b}); } } return res; } int main() { 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]=='*'&&st[i][j]==0) { st[i][j]=1; int now=bfs(i,j); cnt[now]++; } } } int ans1=0,ans2=0; for(int i=1;i<=100000;i++) //计算星系数量和最大星系大小 { if(cnt[i]>0) { ans1++; ans2=max(ans2,i*cnt[i]); } } cout<<ans1<<" "<<ans2<<endl; return 0; }
- 1
Information
- ID
- 2156
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 22
- Accepted
- 6
- Uploaded By