题链
分析
- 如果没有硬石头,显然裸的二分图匹配
- 加上硬石子,相当于分段后跑二分图匹配即可
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=105,M=10005;
int n,m,id1[N][N],id2[N][N],ma[M];
char s[N][N];
vector<int>V[M];
bool fl[M];
bool dfs(int u) {
for(int v:V[u]) {
if(fl[v]) continue;
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u;
return 1;
}
}
return 0;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%s",s[i]+1);
}
int cnt=0;
for(int i=1;i<=n;i++) {
cnt++;
for(int j=1;j<=m;j++) {
if(s[i][j]=='#') {
cnt++;
}
id1[i][j]=cnt;
}
}
cnt=0;
for(int j=1;j<=m;j++) {
cnt++;
for(int i=1;i<=n;i++) {
if(s[i][j]=='#') {
cnt++;
}
id2[i][j]=cnt;
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(s[i][j]=='*') {
V[id2[i][j]].pb(id1[i][j]);
}
}
}
int ans=0;
for(int i=1;i<=cnt;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans++;
}
cout<<ans<<endl;
return 0;
}