大型补档计划
预处理每个列、行连续块。
每个每个列行只能在一个位置匹配，否则冲突。
符合二分图性质，跑匈牙利即可。
点数最坏情况 \(N * M\) （墙空地相间分布），边数最坏情况 \(N * M\) （每个点最多会加一条边），所以复杂度 \(O(N ^ 2M ^ 2)\) 跑得动
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 55;
int n, m, c1, c2, r[N][N], c[N][N], match[N * N];
char g[N][N];
int head[N * N], numE = 0;
bool vis[N * N];
struct E{
int next, v;
} e[N * N];
void add(int u, int v) {
e[++numE] = (E) { head[u], v };
head[u] = numE;
}
bool find(int u) {
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
vis[v] = true;
if (!match[v] || find(match[v])) {
match[v] = u; return true;
}
}
return false;
}
int main() {
int T; scanf("%d", &T);
for (int t = 1; t <= T; t++) {
numE = 0;
memset(match, 0, sizeof match);
memset(head, 0, sizeof head);
scanf("%d%d", &n, &m); c1 = c2 = 0;
for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] != '#') {
if (j > 1 && g[i][j - 1] != '#') r[i][j] = r[i][j - 1];
else r[i][j] = ++c1;
if (i > 1 && g[i - 1][j] != '#') c[i][j] = c[i - 1][j];
else c[i][j] = ++c2;
}
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (g[i][j] == 'o') add(r[i][j], c[i][j]);
int ans = 0;
for (int i = 1; i <= c1; i++) {
memset(vis, false, sizeof vis);
if (find(i)) ans++;
}
printf("Case :%d\n%d\n", t, ans);
}
}