详见进阶指南
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define N 1500 char mp[N][N]; int G[N][N],vis[N],match[N],n,m; bool dfs(int x){ for(int i=1;i<=n;i++) if(!vis[i] && G[x][i]){ vis[i]=1; if(!match[i] || dfs(match[i])){ match[i]=x;return 1; } } return 0; } int work(){ int res=0; memset(match,0,sizeof match); for(int i=1;i<=n;i++){ memset(vis,0,sizeof vis); if(dfs(i))res++; } return res; } int cnt1,cnt2,id1[N][N],id2[N][N];//每个点对应的块序号 int main(){ for(int i=0;i<=55;i++) for(int j=0;j<=55;j++) mp[i][j]='.'; while(scanf("%d%d",&n,&m)!=EOF){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf(" %c",&mp[i][j]);//这样很好用 //标记联通块 cnt1=0,cnt2=0; memset(id1,0,sizeof id1); memset(id2,0,sizeof id2); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]=='*'){ if(mp[i][j-1]==mp[i][j]) id1[i][j]=id1[i][j-1]; else id1[i][j]=++cnt1; if(mp[i-1][j]==mp[i][j]) id2[i][j]=id2[i-1][j]; else id2[i][j]=++cnt2; } //建图 memset(G,0,sizeof G); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]=='*') G[id1[i][j]][id2[i][j]]=1; n=max(cnt1,cnt2); cout<<work()<<endl; } }