记录编号	264095	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1654]放置机器人	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-05-27 15:19:35	内存使用	0.46 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

int n,m,i,j,ans;
int h[110][110]={0},s[110][110]={0};
int p[2510]={0};
bool u[2510]={0};
char c[110][110];
char ch; 
vector <int> l[2510];
vector <int> b;

void makemap(){
	int i=0,j=0,k=0,cnt=0,bh=0;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++){
			if (c[i][j]=='#')	continue;
			if (h[i][j-1]!=0)	h[i][j]=h[i][j-1];
			if (h[i][j]==0)		h[i][j]=++cnt;
			if (c[i][j]=='o')	p[h[i][j]]=1;	}
	 for (i=1;i<=n;i++)
	 	for (j=1;j<=m;j++)
	 	if (p[h[i][j]]==0)	h[i][j]=0;   //横向给区域标号 
	for (i=1;i<=2510;i++)	if (p[i])	b.push_back(i);
	
	memset(p,0,sizeof(p));	cnt=0;
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++){
			if (c[j][i]=='#')	continue;
			if (s[j-1][i]!=0)	s[j][i]=s[j-1][i];
			if (s[j][i]==0)		s[j][i]=++cnt;
			if (c[j][i]=='o')	p[s[j][i]]=1;	}		
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		if (p[s[i][j]]==0)	s[i][j]=0;   //纵向给区域标号 
	memset(p,0,sizeof(p));
	return;
}   //预处理图

bool find(int x){
	int i;
	if (l[x].size()!=0)	
	for (i=0;i<=l[x].size()-1;i++)
	if (not u[l[x][i]])	{
		u[l[x][i]]=1;
		if (p[l[x][i]]==0||find(p[l[x][i]]))	{
		p[l[x][i]]=x;	return 1;}
	}
	return 0;
}   //匈牙利算法 

void work(){
	int i,j;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		if (c[i][j]=='o'&&h[i][j]!=0&&s[i][j]!=0)
		l[h[i][j]].push_back(s[i][j]);   //在交点处连边
	if (b.size()!=0)
	for (i=0;i<=b.size()-1;i++) {
		 memset(u,0,sizeof(u));
		 if (find(b[i]))	ans++;}
	return;
}

int main(){
	freopen("placetherobots.in","r",stdin);
	freopen("placetherobots.out","w",stdout);
	scanf("%d%d",&n,&m);
	i=1;	j=1;
	while (i<=n&&j<=m){
		ch=getchar();
		if (ch=='o'||ch=='#'||ch=='*')	{
			c[i][j]=ch;	j++;
			if (j>m)	{
				j=1;	i++;
			}
		}
	}
	makemap();	work();
	printf("%d\n",ans);
	return 0;
}