codeforces679C Bear and Square Grid（dfs优化）

题意：

给你n*n的矩阵（n<=500），矩阵内有x和.，然后给你一个k

你可以把一个k*k的矩阵内全部变成.

问你最多有多少个.可以联通

思路：

n^2枚举炸的位置，先预处理联通块和区间.的和

每次向右枚举只需要删掉左边一列，加上右边一列

每次枚举的区间是k*k然后扩展一圈（(k+2)*(k+2)）去掉四个角

这些点所在的联通块都是可以连通的

每次把这些联通块加起来，加上k*k的矩阵，减去这个矩阵内原本的.数量（预处理过）

O（n^2*k）

/* ***********************************************
Author        :devil
Created Time  :2016/6/23 15:27:25
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <stdlib.h>
using namespace std;
const int N=510;
char s[N][N];
int sum[N][N];
int mp[N*N];
int vis[N][N];
int cur,id,all,n,k;
int vsc[N*N];
void dfs(int x,int y)
{cur++;vis[x][y]=id;if(s[x-1][y]=='.'&&!vis[x-1][y]) dfs(x-1,y);if(s[x+1][y]=='.'&&!vis[x+1][y]) dfs(x+1,y);if(s[x][y-1]=='.'&&!vis[x][y-1]) dfs(x,y-1);if(s[x][y+1]=='.'&&!vis[x][y+1]) dfs(x,y+1);
}
void push(int x,int y)
{if(!vis[x][y]) return ;if(!vsc[vis[x][y]]) all+=mp[vis[x][y]];vsc[vis[x][y]]++;
}
void pop(int x,int y)
{if(!vis[x][y]) return ;vsc[vis[x][y]]--;if(!vsc[vis[x][y]]) all-=mp[vis[x][y]];
}
int cal(int x,int y)
{return sum[x][y]-sum[x-k][y]-sum[x][y-k]+sum[x-k][y-k];
}
int main()
{//freopen("in.txt","r",stdin);int ans=0;id=1;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%s",s[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];if(s[i][j]=='.') sum[i][j]++;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(s[i][j]=='.'&&!vis[i][j]){cur=0;dfs(i,j);mp[id++]=cur;}for(int i=1;i<=n-k+1;i++){all=0;memset(vsc,0,sizeof(vsc));for(int j=i-1;j<=i+k;j++)for(int l=1;l<=k;l++)push(j,l);for(int j=i;j<i+k;j++)push(j,k+1);ans=max(ans,all+k*k-cal(i+k-1,k));for(int j=1;j<=n-k;j++){for(int l=i;l<i+k;l++){pop(l,j-1);push(l,j+k+1);}pop(i-1,j);pop(i+k,j);push(i-1,j+k);push(i+k,j+k);ans=max(ans,all+k*k-cal(i+k-1,j+k));}}printf("%d\n",ans);return 0;
}