题意：
给出一张图，图中‘X‘表示wall,‘.‘表示空地,可以放置blockhouse同一条直线上只能有一个blockhouse，除非有wall
隔开，问在给出的图中最多能放置多少个blockhous
分析：
把原始图分别按行和列缩点
建图：横竖分区。先看每一列，同一列相连的空地同时看成一个点，显然这样的区域不能够同时放两个点。这些
点作为二分图的X部。同理在对所有的行用相同的方法缩点，作为Y部。
连边的条件是两个区域有相交部分(即‘.‘的地方)。最后求最大匹配就是答案。
#include <bits/stdc++.h> using namespace std; int n; struct node { int a = 0 , b = 0; }; node id[6][6]; char mp[6][6]; bool link[105][105]; bool vis[105]; int use[105]; int hcnt,rcnt; void dfsh(int x,int y){ if(y <= n && mp[x][y] == ‘.‘){ id[x][y].a = hcnt; dfsh(x,y+1); } } void dfsr(int x,int y){ if(x <= n && mp[x][y] == ‘.‘){ id[x][y].b = rcnt; dfsr(x+1,y); } } int find(int x) { for (int s = 1; s < rcnt; s++) { if (link[x][s] && !vis[s]) { vis[s] = 1; if (use[s] == 0 || find(use[s])) { use[s] = x; return 1; } } } return 0; } int main(int argc, char const *argv[]) { while(cin >> n && n){ for(int i = 1;i <= n ;i ++){ cin >> mp[i] + 1; } memset(id,0,sizeof id); memset(link,0,sizeof link); memset(use,0,sizeof use); hcnt = rcnt = 1; for(int i = 1;i <= n;i ++){ for(int j = 1;j <= n ;j ++){ if(mp[i][j] == ‘X‘){ continue; } if(id[i][j].a == 0){ dfsh(i,j); hcnt ++; } if(id[i][j].b == 0){ dfsr(i,j); rcnt ++; } link[id[i][j].a][id[i][j].b] = 1; } } int sum = 0; for(int i = 1;i < hcnt;i ++){ memset(vis,0,sizeof vis); if(find(i)) sum ++; } printf("%d\n",sum ); } return 0; }
原文：https://www.cnblogs.com/DWVictor/p/11343288.html