记录编号	150162	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]部落战争	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2015-02-28 07:49:13	内存使用	0.53 MiB

#include<cstdio>
#include<cstring>
int n,m,r,c,tv,tmp,ans,len,dx[4],dy[4],g[6000],v[6000],pre[6000],to[20001],next[20001],hash[60][60];
char map[60][60];
void add(int x,int y){
	to[++len]=y,next[len]=g[x],g[x]=len;
}
bool dfs(int x){
	for(int t,i=g[x];i;i=next[i]){
		if(v[t=to[i]]!=tv){
			v[t]=tv;
			if(pre[t]==-1||dfs(pre[t]))
				return pre[t]=x,1;
		}
	}
	return 0;
}
int main(){
	freopen("lanzerb.in","r",stdin);
	freopen("lanzerb.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&r,&c),tmp=n*m,tv=1;
	dx[0]=r,dx[1]=r,dx[2]=c,dx[3]=c;
	dy[0]=-c,dy[1]=c,dy[2]=-r,dy[3]=r;
	for(int i=0;i<n;i++) scanf("%s",map[i]);
	for(int k=0,i=0;i<n;i++)
		for(int j=0;j<m;j++)
			hash[i][j]=k++;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++){
			if(map[i][j]=='x') continue;
			ans++;
			for(int k=0;k<4;k++){
				int nx=i+dx[k],ny=j+dy[k];
				if(nx<0||nx>=n||ny<0||ny>=m||map[nx][ny]=='x') continue;
				add(hash[i][j],hash[nx][ny]+tmp);
			}
		}
	memset(pre,-1,sizeof pre);
	for(int i=0;i<tmp;i++,tv++) ans-=dfs(i);
	printf("%d",ans);
}