题解：
匈牙利
每一堆再一起的建边
然后n-最大匹配/2
代码：
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int N=20005; int a[45][45],f[N],cnt,match[N],T,n,m,fi[N],num,zz[N],ne[N]; void jb(int x,int y) { ne[++num]=fi[x]; fi[x]=num; zz[num]=y; ne[++num]=fi[y]; fi[y]=num; zz[num]=x; } int dfs(int x) { for (int i=fi[x];i;i=ne[i]) if (!f[zz[i]]) { f[zz[i]]=1; if (!match[zz[i]]||dfs(match[zz[i]])) { match[zz[i]]=x; return 1; } } return 0; } int main() { scanf("%d",&T); while (T--) { memset(a,0,sizeof a); memset(fi,0,sizeof fi); memset(match,0,sizeof match); num=cnt=0; scanf("%d%d",&n,&m); for (int i=0;i<n;i++) for (int j=0;j<m;j++) { char ch=getchar(); while (ch!='o'&&ch!='*')ch=getchar(); if (ch=='*')a[i][j]=++cnt; else a[i][j]=0; } for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (a[i][j]) { if (a[i+1][j])jb(a[i][j],a[i+1][j]); if (a[i][j+1])jb(a[i][j],a[i][j+1]); } int ans=0; for (int i=1;i<=cnt;i++) { memset(f,0,sizeof f); ans+=dfs(i); } printf("%d ",cnt-ans/2); } return 0; }