Submission #20163715

---

Source Code Expand

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<bitset>
#include<deque>
#include<cstdlib>
#include<set>
#include<ctime>
#define ll long long
#define mp make_pair
using namespace std;
ll read()
{
	ll x=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return f*x;
}
int n,m,fa[1002],ans,st[1002],top,ans2;
char s[1002][1002],c[1002][1002];
bool b[1002];
int getfa(int x)
{
	return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
int main()
{
	n=read(),m=read();
	ans=m-2;
	for(int i=1;i<=m;++i) fa[i]=i;
	for(int i=1;i<=n;++i)
	{
		scanf("%s",s[i]+1); 
	 } 
	b[1]=b[m]=1;
	fa[1]=fa[m]=0;
	for(int i=2;i<m;++i)
	{
		if(s[1][i]=='#'||s[n][i]=='#') b[i]=1,ans--,fa[i]=0;
	}
 
	for(int i=2;i<n;++i)
	{
		top=-1;
		for(int j=1;j<=m;++j) if(s[i][j]=='#')
		{
			if(top==-1) top=getfa(j);
			else
			{
				int tmp=getfa(j);
				if(tmp!=top) fa[tmp]=top,ans--;
			}
		}
	}
	
	
	for(int i=1;i<=n;++i) 
	{
		for(int j=1;j<=m;++j) 
		{
			c[j][i]=s[i][j];
		}
	}
	swap(n,m);
	ans2=m-2;
	for(int i=0;i<=m;++i) fa[i]=i,b[i]=0;
	b[1]=b[m]=1;
	fa[1]=fa[m]=0;
	for(int i=2;i<m;++i)
	{
		if(c[1][i]=='#'||c[n][i]=='#') b[i]=1,ans2--,fa[i]=0;
	}
 
	for(int i=2;i<n;++i)
	{
		top=-1;
		for(int j=1;j<=m;++j) if(c[i][j]=='#')
		{
			if(top==-1) top=getfa(j);
			else
			{
				int tmp=getfa(j);
				if(tmp!=top) fa[tmp]=top,ans2--;
			}
		}
	}
	
	cout<<min(ans,ans2)<<'\n';
	return 0;
 }

Submission Info

Judge Result