题解

我并不会做，我觉得很像网络流但是毫无建图思路

我猜了个贪心，写了一下……啥过了90分？！这数据是有多水啊。。

哦又是行列拆点

不过要按照‘#’进行拆点，也就是一段横着的区间只能放一个炸弹，一段竖着的区间只能放一个炸弹，如果两个区间的交点是一个空格的话，那么就把这两个区间拆出来的点连边

最后我们只要求一下最大匹配就可以了

代码

#include 
    
     #define enter putchar('\n')#define space putchar(' ')#define pii pair
     
      #define fi first#define se second#define MAXN 100005#define pb push_back#define mp make_pair#define eps 1e-8//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {        res = res * 10 + c - '0';        c = getchar();    }}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) out(x / 10);    putchar('0' + x % 10);}int N,M;char s[55][55];int idc[55][55],idr[55][55],Ncnt;struct node {    int to,next;}E[100005];int head[5005],sumE,matc[5005];bool vis[5005];void add(int u,int v) {    E[++sumE].to = v;    E[sumE].next = head[u];    head[u] = sumE;}bool match(int u) {    for(int i = head[u] ; i ; i = E[i].next) {        int v = E[i].to;        if(!vis[v]) {            vis[v] = 1;            if(!matc[v] || match(matc[v])) {                matc[v] = u;                return true;            }        }    }    return false;}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    read(N);read(M);    for(int i = 1 ; i <= N ; ++i) scanf("%s",s[i] + 1);    for(int i = 1 ; i <= N ; ++i) {        ++Ncnt;        for(int j = 1 ; j <= M ; ++j) {            if(s[i][j] == '#') ++Ncnt;            else idr[i][j] = Ncnt;        }    }    for(int j = 1 ; j <= M ; ++j) {        ++Ncnt;        for(int i = 1 ; i <= N ; ++i) {            if(s[i][j] == '#') ++Ncnt;            else idc[i][j] = Ncnt;        }    }    for(int i = 1 ; i <= N ; ++i) {        for(int j = 1 ; j <= M ; ++j) {            if(s[i][j] == '*') add(idr[i][j],idc[i][j]);        }    }    int ans = 0;    for(int i = 1 ; i <= Ncnt ; ++i) {        if(head[i]) {            memset(vis,0,sizeof(vis));            if(match(i)) ++ans;        }    }    out(ans);enter;    return 0;}