题解思路

这道题目可以转化为二分图的最小点覆盖问题。具体步骤如下：

1. 编号处理：

   • 水平编号：对每一行中的连续泥泞区域进行编号，同一连续区域编号相同。
   • 垂直编号：对每一列中的连续泥泞区域进行编号，同一连续区域编号相同。

2. 构建二分图：

   • 将水平编号作为二分图的一边，垂直编号作为另一边。
   • 对于每个泥泞点，连接其水平编号和垂直编号。

3. 匈牙利算法：

   • 使用匈牙利算法求出二分图的最大匹配，该最大匹配数即为所需的最少木板数量。

解决代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>

#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)

using namespace std;

inline LL getint() {
    int f, x = 0;
    char ch = getchar();
    while (ch <= '0' || ch > '9') {
        if (ch == '-') f = -1;
        else f = 1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int maxn = 1000;
struct edge {
    int to, next;
} e[maxn * maxn];
int n, m, cnt, head[maxn], a[maxn][maxn], x[maxn][maxn], y[maxn][maxn], p[maxn], vis[maxn];
char s[maxn];

void insert(int u, int v) {
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

bool find(int x) {
    for (int i = head[x]; i; i = e[i].next) {
        if (!vis[e[i].to]) {
            vis[e[i].to] = 1;
            if (p[e[i].to] == 0 || find(p[e[i].to])) {
                p[e[i].to] = x;
                return true;
            }
        }
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        for (int j = 0; j < m; j++) {
            if (s[j] == '*') a[i][j + 1] = 1;
            else a[i][j + 1] = 0;
        }
    }
    
    int xx = 0, yy = 0;
    // 水平编号
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] > 0) {
                x[i][j] = ++xx;
                while (j < m && a[i][j + 1] > 0) {
                    j++;
                    x[i][j] = xx;
                }
            }
        }
    }
    
    // 垂直编号
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (a[i][j] > 0) {
                y[i][j] = ++yy;
                while (i < n && a[i + 1][j] > 0) {
                    i++;
                    y[i][j] = yy;
                }
            }
        }
    }
    
    // 构建二分图
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] > 0) {
                insert(x[i][j], y[i][j]);
            }
        }
    }
    
    // 匈牙利算法求最大匹配
    int ans = 0;
    for (int i = 1; i <= xx; i++) {
        memset(vis, 0, sizeof(vis));
        if (find(i)) ans++;
    }
    
    printf("%d\n", ans);
    return 0;
}

代码解释

• 输入处理：读取网格的行列数和每个网格的状态（泥泞或草地）。
• 水平编号：对每行中的连续泥泞区域进行编号，同一连续区域编号相同。
• 垂直编号：对每列中的连续泥泞区域进行编号，同一连续区域编号相同。
• 构建二分图：将水平编号和垂直编号作为二分图的两部分，每个泥泞点连接其水平编号和垂直编号。
• 匈牙利算法：通过匈牙利算法求出二分图的最大匹配数，该数即为覆盖所有泥泞区域所需的最少木板数量。
• 输出结果：打印所需的最少木板数量。