大意：如下图告诉你一个矩阵，让你用1 * x (x 为任意值） 的木板去铺符号* 可以覆盖
问最少多少木板能够把所有的*覆盖掉
4 4*.*..******...*. Boards 1, 2, 3 and 4 are placed as follows: 1.2. .333 444. ..2. Board 2 overlaps boards 3 and 4. 分析： 题目要求是把所有的点都覆盖掉 回忆一下之前做过的 这种类型的大概就是二分图的最小点覆盖或者最小边覆盖 那么怎么建立二分图呢 因为X是个不确定值 所以我们尽量让X取值越大越好 也就是说每一个横向或纵向的*区域都可以看做是一个联通块 那么只要把横向的连通块放在左集合，把纵向的连通块放在右集合 把点看左边 那么只要所有的边被覆盖则就是覆盖掉所有的*了 这样想来因为左右集合放的就是所求的连通块，那么只要求出最小点覆盖集即ok啦 最小点覆盖集 = 二分图最大匹配 代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int maxn = 55; 8 int G[maxn * maxn / 2][maxn * maxn / 2]; 9 10 int vis[maxn * maxn / 2];11 int Link[maxn * maxn / 2];12 int n;13 bool Find(int u) {14 for(int i = 1; i <= n; i++) {15 if(G[u][i] && !vis[i]) {16 vis[i] = 1;17 if(Link[i] == -1 || Find(Link[i])) {18 Link[i] = u;19 return true;20 }21 }22 }23 return false;24 }25 26 int solve() {27 int cnt = 0;28 memset(Link, -1, sizeof(Link));29 for(int i = 1; i <= n; i++) {30 memset(vis, 0, sizeof(vis));31 if(Find(i)) cnt++;32 }33 return cnt;34 }35 36 char mat[maxn][maxn];37 int vis1[maxn][maxn], vis2[maxn][maxn];38 int main() {39 int m;40 for(int i = 0; i <= 50; i++) {41 mat[0][i] = mat[i][0] = '.';42 }43 while(EOF != scanf("%d %d",&n, &m)) {44 for(int i = 1; i <= n; i++) {45 for(int j = 1; j <= m; j++) {46 scanf("\n%c",&mat[i][j]);47 }48 }49 int tot1 = 1; int tot2 = 1;50 memset(vis1, 0, sizeof(vis1)); memset(vis2, 0, sizeof(vis2));51 for(int i = 1; i <= n; i++) {52 for(int j = 1; j <= m; j++) {53 if(mat[i][j] == '*') {54 if(!vis1[i][j - 1]) {55 vis1[i][j] = tot1++;56 } else {57 vis1[i][j] = vis1[i][j - 1];58 }59 if(!vis2[i - 1][j]) {60 vis2[i][j] = tot2++;61 } else {62 vis2[i][j] = vis2[i - 1][j];63 }64 }65 }66 }67 memset(G, 0, sizeof(G));68 for(int i = 1; i <= n; i++) {69 for(int j = 1; j <= m; j++) {70 if(mat[i][j] == '*') {71 G[vis1[i][j]][vis2[i][j]] = 1;72 }73 }74 }75 n = max(tot1, tot2);76 printf("%d\n",solve());77 }78 return 0;79 }