看到有人说不考虑软石头会出错这样的错
但是我考虑了啊
#include<bits/stdc++.h>
using namespace std;
#define xztx main
int n , m , ans;
int mp_l[52][52] , mp_h[52][52] , cnt; // # -> -1 ; x -> -2 ; * -> cnt
struct Node{
int next , to;
}e[5000];
int h[5000] , Size;
void add(int a , int b){
e[++ Size].to = b , e[Size].next = h[a] , h[a] = Size;
}
int vis[5000] , col[5000];
bool Find(int x){
// cout <<"--"<< x <<"\n";
for(int i = h[x];i;i = e[i].next){
int y = e[i].to;
if(!vis[y]){
vis[y] = 1;
if(!col[y] || Find(col[y])){
col[x] = y;
return 1;
}
}
}
return 0;
}
int xztx(){
ios :: sync_with_stdio(0);
cin . tie(0);
char c;
cin >> n >> m;
for(int i = 1;i <= n;++ i) mp_h[i][m + 1] = -1;
for(int i = 1;i <= m;++ i) mp_l[n + 1][i] = -1; // 预处理右(下)边一排硬石头
for(int i = 1 , f = 1;i <= n;++ i)
for(int j = 1;j <= m + 1;++ j){
if(j <= m) cin >> c;
if(c == '#') mp_l[i][j] = mp_h[i][j] = -1;
if(c == 'x') mp_l[i][j] = mp_h[i][j] = -2;
if(mp_h[i][j] == -1){// 是硬石头
if(!f) continue; // 且 不是连着的硬石头
f = 0 , ++ cnt;
continue;
}
if(!mp_h[i][j]) mp_h[i][j] = cnt , f = 1;
}
///////////////////////////////////////////////////// 行初始化
for(int i = 1 , f = 1;i <= m;++ i)
for(int j = 1;j <= n + 1;++ j){
if(mp_l[j][i] == -1){// 是硬石头
if(!f) continue; // 且 不是连着的硬石头
f = 0 , ++ cnt;
continue;
}
if(!mp_l[j][i]) mp_l[j][i] = cnt , f = 1;
}
////////////////////////////////////////////////////// 列初始化
// for(int i = 1;i <= n;i ++){
// for(int j = 1;j <= m;j ++){
// cout << mp_h[i][j] <<" ";
// }
// cout << endl;
// }for(int i = 1;i <= n;i ++){
// for(int j = 1;j <= m;j ++){
// cout << mp_l[i][j] <<" ";
// }
// cout << endl;
// }
for(int i = 1;i <= n;++ i){
for(int j = 1;j <= m;++ j){
if(mp_l[i][j] < 0 || mp_h[i][j] < 0){continue;}
// cout<< mp_h[i][j] <<" " << mp_l[i][j] << endl;
add(mp_h[i][j] , mp_l[i][j]);
add(mp_l[i][j] , mp_h[i][j]);
}
}
// cout << 1;
//////////////////////////////////////////// 加边
for(int i = 1;i <= cnt;++ i){
memset(vis , 0 , sizeof vis);
ans += Find(i);
// cout << ans;
}
cout << ans;
return 0;
}
/*
4 4
#*x*
*#**
**#*
xxx#
*/