Codeforces 679 C Bear and Square Grid暴力(スライドウィンドウ)

标题:n*n地図、'X'が障害、'.'周りの隣の'.'に着くことができます.
今チャンスをあげます:あるk*kサブ矩形を選んで中の'X'を'.'に変えます.
n,k<=500.最大の連通成分の中で'.'个数
暴力は変化子矩形の左上隅を列挙し、その子矩形とどのような連通成分があるかを判断する.
サブ矩形の4つの境界を調べるだけでよい.O(n^2*k)
k*kには外部に接続する連通成分がある可能性がある、まずk*kを加えてから、内部でこれらの連通成分の大きさを小さくし、繰り返し計算を防止する.スライドウィンドウの処理でよい.

#include 
using namespace std;
const int N=5e2+20;
int n,k;
char s[N][N],a[N][N];
int ans,cnt,vis[N][N],mk[N*N],c[N*N],pn,b[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y)
{
	if(!vis[x][y])
		b[x][y]=pn,vis[x][y]=1,cnt++;
	for(int i=0;i<4;i++)
	{
		int c=x+dx[i],d=y+dy[i];
		if(c>=1&&c<=n&&d>=1&&d<=n&&!vis[c][d]&&a[c][d]!='X')
			dfs(c,d);
	}
}
int cur,res;
void init()
{
	cur=1;
	pn=ans=0;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(!vis[i][j]&&a[i][j]!='X')
			{
				++pn,cnt=0;
				dfs(i,j);
				c[pn]=cnt;
				ans=max(cnt,ans);
			}
		}
	}
}
void add(int x,int y,int cur)
{
	int id=b[x][y];
	if(id&&mk[id]!=cur)
		mk[id]=cur,res+=c[id];
}
void update(int x,int y)
{
	for(int i=x;i<=x+k-1;i++)
	{
		++c[b[i][y-1]];
		--c[b[i][y+k-1]];
	}
}
void solve(int x,int y)
{
	res=k*k;
	for(int i=y;i<=y+k-1;i++)
		add(x-1,i,cur),add(x+k,i,cur);
	for(int i=x;i<=x+k-1;i++)
		add(i,y-1,cur),add(i,y+k,cur);
	ans=max(ans,res);
}
int main()
{
	while(cin>>n>>k)
	{
		for(int i=1;i<=n;i++)
			scanf("%s",a[i]+1);
		init();
		for(int i=1;i+k-1<=n;i++)
		{
			for(int x=i;x<=i+k-1;x++)
				for(int y=1;y<=k;y++)
					--c[b[x][y]];		
			for(int j=1;j+k-1<=n;j++)
			{
				solve(i,j);
				++cur;
				if(j+k-1!=n)
				update(i,j+1);
			}
			for(int x=i;x<=i+k-1;x++)
				for(int y=n-k+1;y<=n;y++)
					++c[b[x][y]];
		}
		printf("%d
",ans);
	}
	return 0;
}