2 条题解
-
0117爱好者 (mengqingyu) LV 10 @ 2024-7-27 9:47:50
#include<bits/stdc++.h> using namespace std; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; int num[1005][1005],p=0; int fa[1000005]; int size[1000005]; int n,m; char a[1005][1005]; bool vis[1000005]; int find(int x){ if(fa[x]==x){ return x; }else{ return fa[x]=find(fa[x]); } } void merge(int x,int y){ int fx=find(x); int fy=find(y); if(fx==fy){ return ; } if(size[fx]>size[fy]){ fa[fy]=fx; size[fx]+=size[fy]; }else{ fa[fx]=fy; size[fy]+=size[fx]; } } int main(){ cin>>n>>m; for(int i=1;i<=n*m;i++){ fa[i]=i; size[i]=1; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; num[i][j]=(++p); } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]=='.'){ for(int k=0;k<4;k++){ int b,c; b=i+dx[k]; c=j+dy[k]; if(a[b][c]=='.'&&vis[find(num[b][c])]==0){ vis[find(num[b][c])]=1; merge(num[i][j],num[b][c]); } } for(int k=0;k<4;k++){ int b,c; b=i+dx[k]; c=j+dy[k]; vis[find(num[b][c])]=0; } } } } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int sum=0; if(a[i][j]=='*'){ for(int k=0;k<4;k++){ int b,c; b=i+dx[k]; c=j+dy[k]; if(a[b][c]=='.'&&vis[find(num[b][c])]==0){ vis[find(num[b][c])]=1; sum+=size[find(num[b][c])]; } } for(int k=0;k<4;k++){ int b,c; b=i+dx[k]; c=j+dy[k]; vis[find(num[b][c])]=0; } } ans=max(ans,sum+1); } } cout<<ans; return 0; }
-
02024-6-2 20:07:39@
勿抄 不然CE你
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; const int M=1e3+10; int dx[10]={-1,1,0,0},dy[10]={0,0,-1,1}; int num[M][M],p,ans=(-0x3f3f3f3f); int n,m,fa[N],siz[N];//siz存连通分量大小 bool vis[N]; char a[M][M]; void Memset() { for(int i=1;i<=n*m;++i) { fa[i]=i; siz[i]=1; } } int find(int x) { if(fa[x]==x)return x; return fa[x]=find(fa[x]); } void merge(int x,int y) { int fx=find(x),fy=find(y); if(fx==fy)return; if(siz[fx]<siz[fy])//把小的连通分量合并给大的 { fa[fx]=fy;siz[fy]+=siz[fx]; } else { fa[fy]=fx;siz[fx]+=siz[fy]; } } int main() { cin>>n>>m; Memset(); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { cin>>a[i][j]; num[i][j]=(++p); } } for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { if(a[i][j]=='.') { for(int k=0;k<4;++k) { int b=i+dx[k]int c=j+dy[k]; if(a[b][c]=='.') { merge(num[i][j],num[b][c]); } } } } } //把贫瘠变为肥沃 for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { int sum=0 if(a[i][j]=='*') { for(int k=0;k<4;++k) { int b=i+dx[k]; int c=j+dy[k]; if(a[b][c]=='.' && vis[ find(num[b][c]) ]==0) { vis[ find(num[b][c]) =1; sum+=siz[ find(num[b][c]) ]; } } for(int k=0;k<4;++k) { int b=i+dx[k];int c=j+dy[k]; vis[ find(num[b][c) ]=0; } } ans=max(ans,sum+1); } } cout<<ans; return 0; }
- 1
信息
- ID
- 3150
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 24
- 已通过
- 7
- 上传者