题意：一片r*c的地，有些地方是泥地，需要铺地板。这些地板宽1，长无限，但只能铺在泥地上不能压到其他地方，问你铺满所有泥地最少几块
思路：我们把一行中连续的泥地看成整体，并把所有横的整体里的点编成一个id号，同样把竖的所有整体编号，这样一个点就有横竖两个编号，那么我给这两个编号连边，那么只要涂这个边就代表了这个点被模板盖住了，那么问题就转化为了最小点覆盖
代码：
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = + ;
const int MOD = 1e9 + ;
const int INF = 0x3f3f3f3f;
int linker[maxn];
bool used[maxn];
struct node{
int row, col;
}p[maxn][maxn];
int n;
int head[maxn], tot;
struct Edge{
int to, next;
}edge[maxn * maxn];
char mp[maxn][maxn];
void init(){
memset(head, -, sizeof(head));
tot = ;
}
void addEdge(int u, int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
bool dfs(int u){
for(int i = head[u]; i != -; i = edge[i].next){
int v = edge[i].to;
if(!used[v]){
used[v] = true;
if(linker[v] == - || dfs(linker[v])){
linker[v] = u;
return true;
}
}
}
return false;
}
int hungry(){
int res = ;
memset(linker, -, sizeof(linker));
for(int u = ; u <= n; u++){
memset(used, false, sizeof(used));
if(dfs(u)) res++;
}
return res;
}
int main(){
int r, c;
while(~scanf("%d%d", &r, &c)){
n = ;
init();
for(int i = ; i <= r; i++){
scanf("%s", mp[i] + );
for(int j = ; j <= c; j++){
p[i][j].col = p[i][j].row = ;
}
}
for(int i = ; i <= r; i++){
for(int j = ; j <= c; j++){
if(mp[i][j] == '*'){
if(j > && mp[i][j - ] == '*'){
p[i][j].row = p[i][j - ].row;
}
else{
p[i][j].row = ++n;
}
}
}
}
for(int i = ; i <= r; i++){
for(int j = ; j <= c; j++){
if(mp[i][j] == '*'){
if(i > && mp[i - ][j] == '*'){
p[i][j].col = p[i - ][j].col;
}
else{
p[i][j].col = ++n;
}
addEdge(p[i][j].row, p[i][j].col);
}
}
}
printf("%d\n", hungry());
}
return ;
}