考虑每一个脏的位置,可以从左侧扩展一个板子,或者从上侧扩展一个板子,这一个格子的这两个板子至少要选一个。满足最小点覆盖的规律。然后将这两种板子作为左右子集,每个子集中没有边。可以确定这是一个二分图。根据最小点覆盖等于最大匹配求解。代码细节很多具体看代码。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxx=500*500*2;
char mp[505][505];
int k1[505][505],k2[505][505];
int n,m;
struct node{
int to;
int next;
}e[maxx];
int k,head[maxx];
void add(int u,int v){
e[++k].to=v;
e[k].next=head[u];
head[u]=k;
}
int match[maxx],vis[2500],cnt1,cnt2;
void build(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='*'){
if(mp[i][j-1]=='*'){
k1[i][j]=cnt1;
}
else{
cnt1++;
k1[i][j]=cnt1;
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='*'){
if(mp[i-1][j]=='*'){
k2[i][j]=k2[i-1][j];
}
else{
cnt2++;
k2[i][j]=cnt2;
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
add(k1[i][j],k2[i][j]+n*m);
}
}
}
int dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!vis[v]){
vis[v]=1;
if(!match[v]||dfs(match[v])){
match[u]=v;
match[v]=u;
return 1;
}
}
}
return 0;
}
void debug(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<k1[i][j]<<" ";
}
cout<<endl;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<k2[i][j]<<" ";
}
cout<<endl;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<mp[i][j]<<" ";
}
cout<<endl;
}
}
int sum;
int main(){
cin>>n>>m;
build();
// debug();
for(int i=1;i<=cnt1;i++){
if(!match[i]){
memset(vis,0,sizeof(vis));
if(dfs(i)) sum++;
}
}
cout<<sum<<endl;
}