记录编号	190009	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1654]放置机器人	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2015-10-01 09:05:35	内存使用	1.63 MiB

#include<cstdio>
#include<cstring>
int n,m,shu,k,n1,ans,root1[55][55],root2[55][55],first[5555],macth[5555];
char o[55][55];
bool p[5555];
struct bian
{
    int u,v,next;
}c[111111];
inline void add(int u,int v)
{
 	 c[++shu].u=u;
 	 c[shu].v=v;
 	 c[shu].next=first[u];
 	 first[u]=shu;
}
inline bool dfs(int x)
{
    for(int i=first[x];i;i=c[i].next)
 	    if(!p[c[i].v])
        {
	        p[c[i].v]=1;
	 	    if(!macth[c[i].v]||dfs(macth[c[i].v]))
	        {
			 	macth[c[i].v]=x;
                return 1;
            }
		 }
    return 0;
}
int main()
{
 	freopen("placetherobots.in","r",stdin);
 	freopen("placetherobots.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%s",o[i]+1);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(o[i][j]=='o'&&!root1[i][j])
            {
				++shu;
				k=j;
				while(o[i][k]!='#'&&k>=1)
				{									
				    root1[i][k]=shu;
			 	    --k;
				} 
				k=j+1;
				while(o[i][k]!='#'&&k<=m)
				{									
				    root1[i][k]=shu;
			 	    ++k;
				}
				j=k;
			}
    n1=shu;        
	for(int j=1;j<=m;++j)
	    for(int i=1;i<=n;++i)
            if(o[i][j]=='o'&&!root2[i][j])
            {
				++shu;
				k=i;
				while(o[k][j]!='#'&&k>=1)
				{									
				    root2[k][j]=shu;
			 	    --k;
				}
				k=i+1;
				while(o[k][j]!='#'&&k<=n)
				{									
				    root2[k][j]=shu;
			 	    ++k;
				}
				i=k;
			}
    shu=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(o[i][j]=='o'&&root1[i][j]&&root2[i][j])
            {
			    add(root1[i][j],root2[i][j]);
			    add(root2[i][j],root1[i][j]);
			}
    for(int i=1;i<=n1;++i)
    {
	 	memset(p,0,sizeof(p)); 		
        if(dfs(i))
            ++ans;
    }
    printf("%d",ans);
}