题目描述

在一块 N×M 的网格状地面上，有一些格子是泥泞的，其他格子是干净的。

现在需要用一些宽度为 1、长度任意的木板把泥地盖住，同时不能盖住干净的地面。

每块木板必须覆盖若干个完整的格子，木板可以重叠。

求最少需要多少木板。

输入格式
第一行包含两个整数 N 和 M。

接下来 N 行，每行 M 个字符，用来描述地面，* 表示泥泞格子，. 表示干净格子，字符之间没有空格。

输出格式
输出一个整数，表示结果。

数据范围
1≤N,M≤50

样例

4 4
*.*.
.***
***.
..*.

输出答案

4

算法1

与车的放置的升级版有些类似，我们要对每行相邻的泥泞区域编上相同的编号，
然后对每列相邻的泥泞区域编相同的编号，对于重合在一起的编号之间连上边
，这时候求最小点覆盖就能以最少的点覆盖掉所有的边，相当于覆盖掉了所有编上编号的区域，
行和列的编号分开存储，对行和列进行二分图匹配求得最大匹配数==最小点覆盖即可

编号的代码细节可能比较多，多想想几种可能出现的情况

C++ 代码

//与车的放置的升级版有些类似，我们要对每行相邻的泥泞区域编上相同的编号，
//然后对每列相邻的泥泞区域编相同的编号，对于重合在一起的编号之间连上边
//，这时候求最小点覆盖就能以最少的点覆盖掉所有的边，相当于覆盖掉了所有编上编号的区域，
//行和列的编号分开存储，对行和列进行二分图匹配求得最大匹配数 == 最小点覆盖即可
//
//编号的代码细节可能比较多，多想想几种可能出现的情况
//C++ 代码
//有障碍物的地方车会被阻挡
#include<bits/stdc++.h>
using namespace std;
bool ban[1005][1005];
int n, m, t;
int num1[80005], num2[80005];
bool f(int x, int y){
    if (x >= 1 && x <= n&&y >= 1 && y <= m)return 1;
    return 0;
}
inline int p(int x, int y){
    return (x - 1)*m + y;
}
int mp[1005][1005];//为了不重复加边而建的邻接矩阵
vector<int > h[80005];
int pre[80005];
bool vis[80005];
bool dfs(int x){
    vis[x] = 1;
    for (auto to : h[x]){
        if (vis[to])continue;
        vis[to] = 1;
        if (!pre[to] || dfs(pre[to])){
            pre[to] = x;
            pre[x] = to;
            return 1;
        }
    }
    return 0;
}
int main(){

    cin >> n >> m;
    int u, v; char c;
    for (int i = 1; i <= n; i++){
        getchar();
        for (int j = 1; j <= m; j++){
            scanf("%c", &c);
            if (c == '.'){//建图
                ban[i][j] = 1;
            }
        }
    }
    int tot = 1; bool f1 = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){//对每一行相邻的泥泞区域编号
            if (!ban[i][j])num1[p(i, j)] = tot, f1 = 0;
            else{
                if (f1 == 0)++tot, f1 = 1;
            }
        }
        if (f1 == 0)++tot, f1 = 1;
        //cout << tot << endl;
    }
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){//对每一列相邻 的泥泞区域编号
            if (!ban[j][i])num2[p(j, i)] = tot, f1 = 0;
            else{
                if (f1 == 0)++tot, f1 = 1;;
            }
        }
        if (f1 == 0)++tot, f1 = 1;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (!ban[i][j]){
                int x = num1[p(i, j)];
                int y = num2[p(i, j)];
                if (!mp[x][y]){   //对于一个点，我们将这个点上行的编号和列的编号之间连上一条边
                    //这里的mp数组是为了保证每个边只加一次，实际上
                    //这一题每条边一定只加一次，可以去掉这个判断
                    //cout << x << " " << y << endl;
                    mp[x][y] = 1;
                    mp[y][x] = 1;
                    h[x].push_back(y);
                    h[y].push_back(x);
                }
            }
        }
    }
    int cnt = 0;
    for (int i = 1; i <= tot; i++){
        memset(vis, 0, sizeof vis);
        if (!pre[i] && dfs(i)){
            cnt++;
        }
    }
    cout << cnt << endl;
}

}