记录编号	185785	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1654]放置机器人	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.054 s
提交时间	2015-09-09 08:33:51	内存使用	1.77 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
int head[3000],n,m,ans,num1,Num,tot,match[3000],a[51][51];
bool vis[3000];
char ch;
struct dd{
	int c[51];
	int b[51];
	int num;
}jie[4000];
struct df{
	int begin,end,next;
}st[4000];
void add(int x,int y){
	st[++tot].begin=x; st[tot].end=y; st[tot].next=head[x]; head[x]=tot;
}
void Build(){
	int q,w;
	for(int i=1;i<=n;++i){
	   q=i,w=1;
	   while(1==1){
        if(a[w][q]!=1) num1++;
		while(a[w][q]!=1&&w<=m){
			   jie[num1].num++;
			   jie[num1].b[jie[num1].num]=w;
			   jie[num1].c[jie[num1].num]=i;
			   w++;
			}
			w++;
			if(w>m) break;
	  }
	}
	Num=num1;
	for(int i=1;i<=m;++i){
		q=i,w=1;
		while(1==1){
		if(a[q][w]!=1) num1++;
		while(a[q][w]!=1&&w<=n){
				jie[num1].num++;
				jie[num1].b[jie[num1].num]=q;
				jie[num1].c[jie[num1].num]=w;
				w++;
		}
		w++;
		if(w>n) break;
	   }
	}
}
void End(){
	for(int i=1;i<=Num;++i)
	 for(int q=1;q<=jie[i].num;++q)
	  for(int j=Num+1;j<=num1;++j)
	   for(int w=1;w<=jie[j].num;++w)
		if(jie[i].b[q]==jie[j].b[w]&&jie[i].c[q]==jie[j].c[w]&&a[jie[i].b[q]][jie[i].c[q]]==3)
		   add(i,j);
}
bool dfs(int x){
	int w;
	for(int i=head[x];i;i=st[i].next){
	   w=st[i].end;
	   if(!vis[w]){
			vis[w]=1;
            if(!match[w]||dfs(match[w])){
			   match[w]=x;
			   return 1;
	        }
	   }
	}
	return 0;
}
void work(){
	  for(int i=1;i<=num1;++i){
		memset(vis,0,sizeof(vis));
		if(dfs(i)) ans++;
	  }
	  printf("%d",ans);
}
void Work(){
     Build(); End(); work();
}
int main(){
     freopen("placetherobots.in","r",stdin);
    freopen("placetherobots.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;++i)
	 for(int j=1;j<=n;++j){
	   cin>>ch;
	   if(ch=='#'){a[i][j]=1;continue;}
	   if(ch=='*'){a[i][j]=2;continue;}
	   if(ch=='o'){a[i][j]=3;continue;}
	 }
	 Work();
}