#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define ALL(x) (x).begin(), (x).end()
#define endl "\n"
const int MAXNM = 1000*10 + 5; // tối đa n*m
const int INF = 1e9;
int n, m;
vector<string> a;
// ---- Hopcroft-Karp để tìm max matching trên bipartite graph (U size = Hn, V size = Vn) ----
int Hn, Vn; // số nút bên trái (H) và bên phải (V)
vector<vector<int>> adj; // adj[u] = danh sách v bên phải
vector<int> distHK, pairU, pairV;
bool bfsHK(){
queue<int> q;
distHK.assign(Hn+1, INF);
FOR(u,1,Hn){
if(pairU[u]==0){
distHK[u] = 0;
q.push(u);
}
}
bool reachableFreeV = false;
while(!q.empty()){
int u = q.front(); q.pop();
for(int v: adj[u]){
int pu = pairV[v];
if(pu==0){
// tìm được đường tăng
reachableFreeV = true;
} else if(distHK[pu]==INF){
distHK[pu] = distHK[u] + 1;
q.push(pu);
}
}
}
return reachableFreeV;
}
bool dfsHK(int u){
for(int v: adj[u]){
int pu = pairV[v];
if(pu==0 || (distHK[pu]==distHK[u]+1 && dfsHK(pu))){
pairU[u] = v;
pairV[v] = u;
return true;
}
}
distHK[u] = INF;
return false;
}
int hopcroftKarp(){
pairU.assign(Hn+1, 0);
pairV.assign(Vn+1, 0);
distHK.assign(Hn+1, INF);
int matching = 0;
while(bfsHK()){
FOR(u,1,Hn){
if(pairU[u]==0 && dfsHK(u))
matching++;
}
}
return matching;
}
// ----------------------------------------------------------------------------
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
a.resize(n);
FOR(i,0,n-1) cin >> a[i];
// 1) đánh số phân đoạn ngang
vector<vector<int>> h_id(n, vector<int>(m, 0));
Hn = 0;
FOR(i,0,n-1){
int cur = 0;
FOR(j,0,m-1){
if(a[i][j]=='#'){
if(j==0 || a[i][j-1]=='.'){
++Hn;
}
h_id[i][j] = Hn;
}
}
}
// 2) đánh số phân đoạn dọc
vector<vector<int>> v_id(n, vector<int>(m, 0));
Vn = 0;
FOR(j,0,m-1){
FOR(i,0,n-1){
if(a[i][j]=='#'){
if(i==0 || a[i-1][j]=='.'){
++Vn;
}
v_id[i][j] = Vn;
}
}
}
// 3) build bipartite graph
adj.assign(Hn+1, {});
FOR(i,0,n-1) FOR(j,0,m-1){
if(a[i][j]=='#'){
int u = h_id[i][j];
int v = v_id[i][j];
adj[u].push_back(v);
}
}
// 4) max matching = min tape segments
int ans = hopcroftKarp();
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |