题目链接：
https://vjudge.net/problem/POJ-2226
题目大意：
用宽度为1长度不限的木板将水洼‘*’盖住而不盖住草‘.'
Sample Input
4 4
*.*.
.***
***.
..*.
Sample Output
4
解题思路：
这道题的构图方法十分巧妙，如果有连续的水洼，假设是横排的，那么这几个连续的水洼可以拿一个板子来覆盖，同样，如果竖排也有连续的水洼，那么也可以拿一个板子来覆盖。这样，当一个水洼既可以拿横着的板子，也可以拿竖着的板子覆盖时，就是相交了。那么这个交线就代表了一个水洼，它既可以被横着盖，也可以被竖着盖。现在我们把所有横排的水洼作为1个水洼需要1个木板，竖着的也同理。
有两种覆盖的方法，一种为横着盖一种为竖着盖覆盖后可转化为下图形式
横着盖：（图中数字表示用的是第几块木板）
1.2.
.333
444.
. . 5.
将这些点加入到X序列中
竖着盖：
1.2.
.324
532.
. . 2.
将这些点加入到Y序列中
将图中水洼进行编号一共有九个水洼
1.2.
.345
678.
. . 9.
9号水洼（5， 2）表示九号水洼可由横着的5号木板覆盖也可以由竖着的2号木板覆盖，5号木板和2号木板之间就有一条线
这样就组成一个二分图，最后求最小的顶点覆盖。就是等于保证每个泥地都被横着的木板或者竖着的木板覆盖了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn = + ; int cx[maxn], cy[maxn];
bool vis[maxn];
vector<int>G[maxn];
int x, y;
//x表示二分图X部的点数
//y表示二分图Y部的点数
bool dfs(int u)
{
for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
if(!vis[v])//如果该点还没进入增广路
{
vis[v] = ;//加入增广路
if(cy[v] == - || dfs(cy[v]))
{
cx[u] = v;
cy[v] = u;
return ;
}
}
}
return ;
} int maxmatch()
{
int ans = ;
memset(cx, -, sizeof(cx));
memset(cy, -, sizeof(cy));
for(int i = ; i <= x; i++)
{
if(cx[i] == -)
{
memset(vis, , sizeof(vis));
ans += dfs(i);
}
}
return ans;
}
char Map[][];
int cnt[][], n, m;
void Build()//建图巧妙
{
int a[][], b[][];
memset(a, , sizeof(a));
memset(b, , sizeof(b));
//木板横着放
x = , y = ;
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
if(Map[i][j] == '*')
{
if(Map[i][j - ] == '*')
a[i][j] = a[i][j - ];
else a[i][j] = ++x;
}
}
}
//木板竖着放
for(int j = ; j < m; j++)
{
for(int i = ; i < n; i++)
{
if(Map[i][j] == '*')
{
if(Map[i - ][j] == '*')
b[i][j] = b[i - ][j];
else b[i][j] = ++y;
//cout<<a[i][j]<<" "<<b[i][j]<<endl;
//建边
G[a[i][j]].push_back(b[i][j]);
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = ; i < n; i++)
{
cin >> Map[i];
}
Build();
cout<<maxmatch()<<endl;
return ;
}