P2825 题解

首先我们考虑没有硬石头的情况。

因为一行只能放一个炸弹，一列也只能放一个炸弹，这和二分图极为相似，我们可以把行和列作为左右节点，建立二分图，进行最大匹配。这是二分图的基本模型。

二分图的建立方法是，把能放炸弹的节点行列进行连边，这样因为二分图匹配的性质，满足每行每列只能放一个。

但是这题加入了硬石头的限制，不那么容易放。其实做法很简单，我们可以根据硬石头的分隔进行离散化。考虑在原来拆分的基础上，把硬石头和硬石头之间分成一行，或者把硬石头和边界之间分成一行。

我们先处理出每个格子属于分隔后的第几“列”，再边处理“行”边进行二分图的建边，最后跑一遍匈牙利就解决了。

#include<bits/stdc++.h>
using namespace std;
int n, m, N, M, q, a[100005], vis[100005], lcnt = 1, ccnt = 1, ans;
char mp[55][55];
map<pair<int, int>, int> rw;
vector<int> G[100005];
bool dfs(int u, int t){//匈牙利算法
    if (vis[u] == t)
        return 0;
    vis[u] = t;
    for (auto &v : G[u])
        if (!a[v] || dfs(a[v], t)){
            a[v] = u;
            return 1;
        }
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> mp[i][j];
    for (int j = 1; j <= M; j++){//注意把 N 和 M 反过来
        for (int i = 1; i <= N; i++){
            if (mp[i][j] == '*')//能放
                rw[make_pair(i, j)] = ccnt;//记录这个格子属于第几“列”
            else if (mp[i][j] == '#')
                ccnt++;//遇到硬石头，新开一列
        }
        ccnt++;//遇到边界，新开一列
    }
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= M; j++){//行同理
            if (mp[i][j] == '*')
                G[lcnt].push_back(rw[make_pair(i, j)]);
            else if (mp[i][j] == '#')
                lcnt++;
        }
        lcnt++;
    }
    for (int i = 1; i < lcnt; i++)//进行匹配
        if (dfs(i, i))
            ans++;
    cout << ans;
}