记录编号	416835	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 游戏	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2017-06-22 20:12:09	内存使用	65.83 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2510,E=1e6+10;
int n,m,x[N][N],y[N][N],idx,idy,match[N];
char s[N][N],okx[N],oky[N];
int w[E],head[E],next[E];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int vis[N],C;
bool find(int x){
	for (int i=head[x];i;i=next[i])
	if (vis[w[i]]!=C){
		int v=w[i];
		vis[v]=C;
		if (!match[v]||find(match[v])){
			match[v]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	freopen("heoi2016_game.in","r",stdin);
	freopen("heoi2016_game.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=0;i<=n+1;i++)
	for (int j=0;j<=m+1;j++)
		s[i][j]='#';
	for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	if (s[i][j]!='#'){
		x[i][j]=(s[i][j-1]=='#'?++idx:x[i][j-1]);
		y[i][j]=(s[i-1][j]=='#'?++idy:y[i-1][j]);
		if (s[i][j]=='*') add(x[i][j],y[i][j]);
	}
	int ans=0;
	for (int i=1;i<=idx;i++) C++,ans+=find(i);
	printf("%d\n",ans);
	return 0;
}