二分图匹配，建图方式巧妙，横向连通块（在一行，中间没有障碍物）、纵向连通块分别为x,y部，相交的连边，求最大匹配。
#include#include #define MAXN 4int n,a[MAXN+10][MAXN+10],cnt,cnt1,c[MAXN*MAXN*2+10],ans;char s[MAXN+2][MAXN+2];bool vis[MAXN*MAXN*2+10];struct node{ int v; node *next;}edge[MAXN*MAXN*MAXN*MAXN*2+10],*adj[MAXN*MAXN*2+10],*ecnt=edge;void addedge(int u,int v){ node *p=++ecnt; p->v=v; p->next=adj[u]; adj[u]=p;}bool dfs(int u){ int v; for(node *p=adj[u];p;p=p->next){ v=p->v; if(!vis[v]){ vis[v]=1; if(!c[v]||dfs(c[v])){ c[u]=v; c[v]=u; return 1; } } } return 0;}void maxmatch(){ for(int i=1;i<=cnt1;i++){ memset(vis,0,sizeof vis); if(!c[i]&&dfs(i)) ans++; }}int main(){ int i,j; while(scanf("%d",&n)){ if(!n) return 0; memset(c,0,sizeof c); memset(adj,0,sizeof adj); memset(a,0,sizeof a); ans=cnt=0; ecnt=edge; for(i=1;i<=n;i++) scanf("%s",s[i]+1); for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(s[i][j]!='.') continue; if(s[i][j-1]!='.') cnt++; a[i][j]=cnt; } cnt1=cnt; for(j=1;j<=n;j++) for(i=1;i<=n;i++){ if(s[i][j]!='.') continue; if(s[i-1][j]!='.') cnt++; addedge(a[i][j],cnt); addedge(cnt,a[i][j]); } maxmatch(); printf("%d\n",ans); }}