记录编号	191061	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1654]放置机器人	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2015-10-06 10:50:19	内存使用	2.34 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
const int SIZEN=60,SIZEM=SIZEN*SIZEN;
int N,M;
class poi
{
public:
	int x,y;
}P[SIZEM];
int mp[SIZEN][SIZEN]={0},shu[SIZEN][SIZEN]={0},heng[SIZEN][SIZEN]={0};
int f[SIZEM]={0};
bool co[SIZEM];
int tot=0,S=0,H=0;
deque<int> s[SIZEM];
void read()
{
	scanf("%d%d",&N,&M);
	char ch;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
		{
			scanf("%c",&ch);
			while(ch!='o'&&ch!='*'&&ch!='#') scanf("%c",&ch);
			if(ch=='o')
			{
				mp[i][j]=0;
				tot++;
				P[tot].x=i;P[tot].y=j;
			}
			else if(ch=='*') mp[i][j]=1;
			else if(ch=='#') mp[i][j]=2;
			else cout<<"error"<<endl;
		}
}
void dfs1(int x,int y,int t)//将竖着的格进行编号
{
	if(mp[x][y]==2||x==0||x==N+1||shu[x][y]==t) return;
	shu[x][y]=t;
	dfs1(x+1,y,t);
	dfs1(x-1,y,t);
}
void dfs2(int x,int y,int t)
{
	if(mp[x][y]==2||y==0||y==M+1||heng[x][y]==t) return;
	heng[x][y]=t;
	dfs2(x,y+1,t);
	dfs2(x,y-1,t);
}
bool find(int x)
{
	//cout<<"x:"<<x<<endl;
	for(int i=0;i<s[x].size();i++)
	{
		int w=s[x][i];
		if(co[w]==0)
		{
			co[w]=1;
			if(f[w]==0||find(f[w])==1)
			{
				f[w]=x;
				return 1;
			}
		}
	}
	return 0;
}
void work()
{
	for(int i=1;i<=tot;i++)
		if(shu[P[i].x][P[i].y]==0)
		{
			S++;
			dfs1(P[i].x,P[i].y,S);
		}
	for(int i=1;i<=tot;i++)
		if(heng[P[i].x][P[i].y]==0) 
		{
			H++;
			dfs2(P[i].x,P[i].y,H);
		}
	for(int i=1;i<=tot;i++)
		s[shu[P[i].x][P[i].y]].push_back(heng[P[i].x][P[i].y]);
	int ans=0;
	for(int i=1;i<=S;i++)
	{
		memset(co,0,sizeof(co));
		//cout<<"i:"<<i<<endl;
		if(find(i)==1) ans++;
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("placetherobots.in","r",stdin);
	freopen("placetherobots.out","w",stdout);
	read();
	work();
	return 0;
}