提交记录 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2010;
int N,M,n,m,ans,cnt,p[maxn],head[maxn];
pair<int,int>id[maxn][maxn];
char a[maxn][maxn];
bool vis[maxn];
struct E{
    int to,next;
}edge[maxn*maxn];
void add(int u,int v){
    edge[++cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;
}
bool dfs(int x){
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(vis[y])continue;
        vis[y]=1;
        if(!p[y]||dfs(p[y])){
            p[y]=x;
            return true;
        }
    }return false;
}
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    cin>>N>>M;cin.get();
    n=m=1;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            a[i][j]=cin.get();
        }cin.get();
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(a[i][j]=='#')continue;
            if(a[i][j-1]=='#')n++;
            id[i][j].first=n;
        }n++;
    }
    for(int j=1;j<=M;j++){
        for(int i=1;i<=N;i++){
            if(a[i][j]=='#')continue;
            if(a[i-1][j]=='#')m++;
            id[i][j].second=m;
        }m++;
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(a[i][j]=='*')add(id[i][j].first,id[i][j].second);
        }
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))ans++;
    }
    cout<<ans;
    return 0;
}