信息
- ID
- 3150
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 25
- 已通过
- 7
- 上传者
#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;
}
#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;
}