记录编号	172593	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1654]放置机器人	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2015-07-25 17:15:01	内存使用	1.51 MiB

#include<cstdio>
#include<cstring>

using namespace std;

char s[60][60];bool v[2600];
int a[60][60][4];//a[i][j][0] 行 a[i][j][1] 列 
int n,m,hang,lie,match[2600],tot,first[2600],sum,ans;

struct Edge{
    int qd,zd,next;
}edge[100000];

void init()
{    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);       
}

void add(int qd,int zd)
{
     edge[++tot].qd=qd;
     edge[tot].zd=zd;
     edge[tot].next=first[qd];
     first[qd]=tot;
}

void makegrafh()
{
     for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=m;j++)
         {
             if(s[i][j]=='o'&&!a[i][j][0])
             {
                 a[i][j][0]=1;
                 a[i][j][2]=++sum;
                 int k;
                 for(k=j+1;k<=m;k++)
                 {
                     if(s[i][k]=='#')
                         break;
                     else
                         if(s[i][k]=='o')
                         {    
                             a[i][k][0]=1;
                             a[i][k][2]=sum;
                         }
                 }
                 j=k;
             }
         }
     }
     hang=sum;
     for(int i=1;i<=m;i++)
         for(int j=1;j<=n;j++)
         {
             if(s[j][i]=='o'&&!a[j][i][1])
             {
                 int k;
                 a[j][i][1]=1;
                 a[j][i][3]=++sum;
                 for(k=j+1;k<=n;k++)
                 {
                     if(s[k][i]=='#')
                         break;
                     else
                         if(s[k][i]=='o')
                         {
                             a[k][i][1]=1;
                             a[k][i][3]=sum;
                         }
                 }
                 j=k;
             }
         }
     for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++)
         {
             if(s[i][j]=='o')
             {    
                  add(a[i][j][2],a[i][j][3]);
                  add(a[i][j][3],a[i][j][2]);
             }
         }
}

bool dfs(int x)
{
     for(int i=first[x];i;i=edge[i].next)
     {
         int zd=edge[i].zd;
         if(!v[zd])
         {
             v[zd]=1;
             if(!match[zd]||dfs(match[zd]))
             {
                 match[zd]=x;
                 return 1;
             }
         }
     }
     return 0;
}

int main()
{
    freopen("placetherobots.in","r",stdin);
    freopen("placetherobots.out","w",stdout);
    init();
    makegrafh();
    for(int i=1;i<=hang;i++)
    {
        memset(v,0,sizeof(v));
        if(dfs(i))
            ans++;
    }
    printf("%d",ans);
    /*for(int i=1;i<=tot;i++)
    {
        printf("%d %d\n",edge[i].qd,edge[i].zd);
    }*/
    /*printf("%d %d\n",hang,sum);
    for(int i=1;i<=n;i++)
    {
        printf("\n");
        for(int j=1;j<=m;j++)
            printf("%d %d ",a[i][j][2],a[i][j][3]);     
    }*/
}
/* 输入文件的第一行有两个正整数m,n（1<=m,n<=50），即地图的行数和列数。
接下来有m行，每行n个字符，这些字符是'#','*'或'o'，它们分别代表墙，草和空地。 */