记录编号	471431	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]部落战争	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2017-11-06 14:26:29	内存使用	0.95 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define maxn 5010
#define maxx 50005
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline void read(int& x)
{	char c=getchar();x=0;int y=1;
	while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=y;
}
const int inf=0x7fffffff;
inline int m_min(int x,int y){return x<y?x:y;}
int n,m,C,R,cnt,num,hea[maxn],dp[maxn],A[55][55],id[55][55],S,T,dx[6],dy[6],fans;
std::queue<int>Q;
inline void readchar(char& c){c=0;for(;c!='.'&&c!='x';c=getchar());}
struct road{int en,cap,nex;}ro[maxx];
inline void add(int x,int y,int z)
{	ro[num].en=y;ro[num].cap=z;ro[num].nex=hea[x];hea[x]=num++;
	ro[num].en=x;ro[num].cap=0;ro[num].nex=hea[y];hea[y]=num++;
}
inline void Clear(std::queue<int>& x){std::queue<int> tmp;std::swap(tmp,x);}
inline bool bfs(int x,int t)
{	Clear(Q);mem(dp,0);dp[x]=1;Q.push(x);
	while(!Q.empty())
	{	int u=Q.front();Q.pop();
		for(int i=hea[u];i!=-1;i=ro[i].nex)
		{	int v=ro[i].en;
			if(!dp[v]&&ro[i].cap)
			{	dp[v]=dp[u]+1;Q.push(v);
				if(v==t) return 1;
			}
		}	
	}
	return 0;
}
inline int dfs(int x,int t,int flow)
{	if(x==t) return flow;
	int f,tmp=0;
	for(int i=hea[x];i!=-1;i=ro[i].nex)
	{	int v=ro[i].en;	
		if(dp[v]==dp[x]+1&&ro[i].cap)
		{	f=dfs(v,t,m_min(flow-tmp,ro[i].cap));
			if(!f){dp[v]=0;continue;}
			ro[i].cap-=f;ro[i^1].cap+=f;tmp+=f;
			if(tmp==flow) return tmp;
		}
	}
	return tmp;
}
int main()
{   freopen("lanzerb.in","r",stdin);
	freopen("lanzerb.out","w",stdout);
	read(n);read(m);read(R);read(C);mem(hea,-1);char c=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{	readchar(c);
			if(c=='.')
			{	A[i][j]=1;
				id[i][j]=++cnt;
			}
		}
	S=(cnt<<1)+1;T=(cnt<<1)+2;
	dx[1]=R;dx[2]=C;dx[3]=R;dx[4]=C;
	dy[1]=C;dy[2]=R;dy[3]=-C;dy[4]=-R;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(A[i][j])
				for(int k=1;k<=4;++k)
				{	int tx=i+dx[k],ty=j+dy[k];
					if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&A[tx][ty])
						add(id[i][j],cnt+id[tx][ty],1);
				}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(A[i][j]) add(S,id[i][j],1),add(cnt+id[i][j],T,1);
	while(bfs(S,T)) fans+=dfs(S,T,inf);
	printf("%d",cnt-fans);
	return 0;
}