记录编号	272329	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1654]放置机器人	最终得分	100
用户昵称	Tiny	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-06-16 20:17:19	内存使用	18.20 MiB

#include "bits/stdc++.h"
namespace xiaoxiao{
	using namespace std;

	namespace _Primary_{
		#define FO(x) (freopen(#x".in","r",stdin),freopen(#x".out","w",stdout))
		#define FC (fclose(stdin),fclose(stdout))
		#define test(x) (freopen(#x".txt","r",stdin))

		#define ifor(a,b,c) for(int a=(b);a<=(c);++a)
		#define dfor(a,b,c) for(int a=(b);a>=(c);--a)

		#define Max(a,b) ((a)>(b)? (a):(b))
		#define Min(a,b) ((a)<(b)? (a):(b))

		typedef unsigned U;
		typedef long long LL;
		typedef unsigned long long ULL;
	}
	using namespace _Primary_;

	namespace QRW{
		#define _jud(ch) ch=getchar(),ch>='0'&&ch<='9'

		inline LL QR(){
			char _ch;
			bool _minus=0;
			LL _num=0;
			while(_ch=getchar(),_ch<'-'||_ch>'9');
			if(_ch=='-') _minus=1,_ch=getchar();
			while(_num=_num*10+_ch-48,_jud(_ch));
			if(_minus) return -_num;
			return _num;
		}

		inline void QW(LL _num,char _ch){
			if(_num<0) _num=-_num,putchar('-');
			int __cnt=0;
			string _str;
			while(_str[++__cnt]=_num%10+'0',_num/=10);
			while(putchar(_str[__cnt]),--__cnt);
			putchar(_ch);
		}

		inline double FQR(){
			char _ch;
			bool _minus=0;
			int __cnt=0;
			double _num=0;
			while(_ch=getchar(),_ch<'-'||_ch>'9');
			if(_ch=='-') _minus=1,_ch=getchar();
			while(_num=_num*10+_ch-48,_jud(_ch));
			if(_ch=='.'){
				_ch=getchar();
				while(_num+=1.0*(_ch-48)/pow(10,++__cnt),_jud(_ch));
			}
			if(_minus) return -_num;
			return _num;
		}
	}
	using namespace QRW;
}
using namespace xiaoxiao;

#define ma 1050
int n,m,ans=0;
char P[ma][ma]={"\0"};
int row[ma][ma][2]={0};//0横标记 1纵标记 2横编号 3纵编号
int cnt1=0,cnt2=0;
int match[ma]={0};
bool vis[ma]={0};
struct Edge{int to,next;}E[ma*ma];
int head[ma]={0},tot=0;

inline void AE(int from,int to){
	E[++tot].to=to,E[tot].next=head[from],head[from]=tot;
}

inline bool Find(int x){
	for(int i=head[x];i;i=E[i].next){
		int p=E[i].to;
		if(!vis[p]){
			vis[p]=1;
			if(match[p]==-1||Find(match[p])){
				match[p]=x;
				return 1;
			}
		}
	}
	return 0;
}

inline void Line(){
	ifor(i,1,n)	ifor(j,1,m){
		if(row[i][j][0]==0&&(P[i][j]=='o'||P[i][j]=='*')){
			row[i][j][0]=++cnt1;
			int tmp=j;
			while(row[i][tmp++][0]=cnt1,P[i][tmp]=='o'||P[i][tmp]=='*');
		}
	}
}

inline void Row(){
	ifor(j,1,m) ifor(i,1,n){
		if(row[i][j][1]==0&&(P[i][j]=='o'||P[i][j]=='*')){
			row[i][j][1]=++cnt2;
			int tmp=i;
			while(row[tmp++][j][1]=cnt2,P[tmp][j]=='o'||P[tmp][j]=='*');
		}
	}
}

int main(){
	FO(placetherobots);

	memset(match,-1,sizeof(match));
	n=QR(),m=QR();
	ifor(i,1,n) scanf("%s",P[i]+1);
	Line(),Row();
	ifor(i,1,n) ifor(j,1,m)	if(P[i][j]=='o') AE(row[i][j][0],row[i][j][1]);
	ifor(i,1,cnt1+cnt2){
		memset(vis,0,sizeof(vis));
		ans+=Find(i);
	}
	QW(ans,'\n');

	FC;
	return 0;
}