C++(g++ 7.5.0) 解法, 执行用时: 6ms, 内存消耗: 528K, 提交时间: 2022-08-22 17:19:03

#include <bits/stdc++.h>
#define il inline
#define vd void
#define rg register
#define rep(i,x,y) for(rg int i=x;i<=y;++i)
#define drp(i,x,y) for(rg int i=x;i>=y;--i)
using namespace std;
const int Len=2333333;
char buf[Len],*p1=buf,*p2=buf,duf[Len],*q1=duf;
il char gc(); il int rd(); il vd pc(char c); il vd rt(int x); il vd flush();
int n,m,l,r,cnt,ans,idx[55][55],idy[55][55],h[5005],vis[5005],lk[5005];
char a[55][55];
struct E{int to,nxt;}e[5005];
il vd Add(int u,int v){e[++cnt]=(E){v,h[u]},h[u]=cnt;}
il char Get(){char c;
    while((c=gc())!='#'&&c!='*'&&c!='o');
    return c;
}
int Link(int u){
    for(rg int i=h[u];i;i=e[i].nxt){int v=e[i].to;
        if(!vis[v]){
            vis[v]=1;
            if(!lk[v]||Link(lk[v])) return lk[v]=u,1;
        }
    }
    return 0;
}
int main(){
    for(rg int T=rd(),o=1;o<=T;++o){
        n=rd(),m=rd(),l=r=ans=cnt=0;
        rep(i,0,n) rep(j,0,m) idx[i][j]=idy[i][j]=0;
        rep(i,1,n) rep(j,1,m) a[i][j]=Get();
        rep(i,1,n) a[i][0]='#';
        rep(i,1,m) a[0][i]='#';
        rep(i,1,n) rep(j,1,m) if(a[i][j]=='o'){
            int x=i,y=j;
            while(a[x][j]!='#') --x;
            if(!idx[x][j]) idx[x][j]=++l;
            while(a[i][y]!='#') --y;
            if(!idy[i][y]) idy[i][y]=++r;
        }
        r+=l;
        rep(i,1,r) h[i]=0;
        rep(i,1,n) rep(j,1,m) if(a[i][j]=='o'){
            int x=i,y=j;
            while(a[x][j]!='#') --x;
            while(a[i][y]!='#') --y;
            Add(idx[x][j],idy[i][y]+l),Add(idy[i][y]+l,idx[x][j]);
        }
        rep(i,l+1,r) lk[i]=0;
        rep(i,1,l){
            rep(j,l+1,r) vis[j]=0;
            ans+=Link(i);
        }
        printf("Case :%d\n%d\n",o,ans);
    }
    return flush(),0;
}
 
il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,Len,stdin),p1==p2)?-1:*p1++;}
il int rd(){char c;
    while(!isdigit(c=gc())&&c!='-');
    int f=c=='-'?c=gc(),1:0,x=c^48;
    while(isdigit(c=gc())) x=((x+(x<<2))<<1)+(c^48);
    return f?-x:x;
}
il vd pc(char c){q1==duf+Len&&fwrite(q1=duf,1,Len,stdout),*q1++=c;}
il vd rt(int x){x<0?pc('-'),x=-x:0,pc((x>=10?rt(x/10),x%10:x)+48);}
il vd flush(){fwrite(duf,1,q1-duf,stdout);}

C++11(clang++ 3.9) 解法, 执行用时: 44ms, 内存消耗: 14308K, 提交时间: 2020-03-02 12:22:22

#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 1255
char map[MAX][MAX];
int colx[MAX][MAX],rowx[MAX][MAX];
bool path[MAX][MAX],visit[MAX];
int match[MAX];
bool SearchPath(int s,int m)
{
	for(int i=0;i<m;++i)
	{
		if(path[s][i]&&!visit[i])
		{
			visit[i]=true;
			if(match[i]==-1||SearchPath(match[i],m))
			{
				match[i]=s;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	int n,m,row,col,cas;
	scanf("%d",&cas);
	for(int t=1;t<=cas;++t)
	{
		scanf("%d%d",&n,&m);
		getchar();
		for(int i=0;i<n;++i)
		gets(map[i]);
		row=col=0;
	    memset(colx,-1,sizeof(colx));
	    memset(rowx,-1,sizeof(rowx));
	    for(int i=0;i<n;++i)
	    {
	    	for(int j=0;j<m;++j)
	    	{
	    		if(map[i][j]!='#'&&rowx[i][j]==-1)
	    		{
	    			for(int k=j;map[i][k]!='#'&&k<m;++k)
	    			rowx[i][k]=row;
	    			++row;
				}
				if(map[i][j]!='#'&&colx[i][j]==-1)
				{
					for(int k=i;map[k][j]!='#'&&k<n;++k)
					colx[k][j]=col;
					++col;
				}
			}
		}
		memset(path,false,sizeof(path));
		for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
		if(map[i][j]=='o'&&rowx[i][j]!=-1&&colx[i][j]!=-1)
		path[rowx[i][j]][colx[i][j]]=true;
		int summ=0;
		memset(match,-1,sizeof(match));
		for(int i=0;i<row;++i)
		{
			memset(visit,false,sizeof(visit));
			if(SearchPath(i,col))
			summ++;
		}
		printf("Case :%d\n%d\n",t,summ);
	}
	return 0;
}