记录编号	142481	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]部落战争	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2014-12-09 15:25:47	内存使用	0.40 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEn=60,SIZEN=5010;
int N;
vector<int> c[SIZEN];
int match[SIZEN]={0};
bool vis[SIZEN]={0};
int findpath(int x){
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i];
		if(!vis[u]){
			vis[u]=true;
			if(match[u]==-1||findpath(match[u])){
				match[u]=x;
				return true;
			}
		}
	}
	return false;
}
int Hungary(void){
	memset(match,-1,sizeof(match));
	int ans=0;
	for(int i=0;i<N;i++){
		memset(vis,0,sizeof(vis));
		if(findpath(i)) ans++;
	}
	return ans;
}
void addedge(int a,int b){c[a].push_back(b);}
int n,m,sR,sC;//本程序中n行m列,和原题相反
int tot=0;
int hash(int i,int j){
	return i*m+j;
}
char board[SIZEn][SIZEn]={0};
int dx[5],dy[5];
void makegraph(void){
	dx[0]= sR,dx[1]= sR,dx[2]= sC,dx[3]= sC;
	dy[0]=-sC,dy[1]= sC,dy[2]=-sR,dy[3]= sR;
	N=n*m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(board[i][j]=='x') continue;
			tot++;
			for(int d=0;d<4;d++){
				int i1=i+dx[d],j1=j+dy[d];
				if(0<=i1&&i1<n&&0<=j1&&j1<m){
					if(board[i1][j1]=='x') continue;
					addedge(hash(i,j),hash(i1,j1)+N);
				}
			}
		}
	}
}
void read(void){
	scanf("%d%d%d%d",&n,&m,&sR,&sC);
	for(int i=0;i<n;i++) scanf("%s",board[i]);
}
int main(){
	freopen("lanzerb.in","r",stdin);
	freopen("lanzerb.out","w",stdout);
	read();
	makegraph();
	printf("%d\n",tot-Hungary());
	return 0;
}