不错的 dp。
考虑按行从上往下 dp,并且把列的连通状态塞进 dp 状态里面。实际上就是塞一个并查集。
判状态合法性就是当一个竖的全黑长条结束后,有没有跟别的列连起来。
code
// Problem: Ex - Unite
// Contest: AtCoder - AtCoder Beginner Contest 296
// URL: https://atcoder.jp/contests/abc296/tasks/abc296_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
typedef vector<int> vi;
const int maxn = 140;
int n, m, ntot, fa[maxn], g[maxn], f[maxn][maxn][500];
char s[maxn][maxn];
map<vi, int> mp;
vi pm[500];
bool vis[10];
inline int ID(vi v) {
if (mp.find(v) != mp.end()) {
return mp[v];
} else {
++ntot;
pm[ntot] = v;
return mp[v] = ntot;
}
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
}
}
void solve() {
scanf("%d%d", &n, &m);
int L = 1e9, R = -1;
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i]);
for (int j = 0; j < m; ++j) {
if (s[i][j] == '#') {
L = min(L, i);
R = max(R, i);
}
}
}
if (R == -1) {
puts("0");
return;
}
vi t;
for (int i = 0; i < m; ++i) {
t.pb(i);
}
mems(f, 0x3f);
f[L - 1][0][ID(t)] = 0;
for (int i = L; i <= R; ++i) {
for (int S = 0; S < (1 << m); ++S) {
for (int j = 1; j <= ntot; ++j) {
if (f[i - 1][S][j] > 1e9) {
continue;
}
int sta = 0;
for (int k = 0; k < m; ++k) {
if (s[i][k] == '#') {
sta |= (1 << k);
}
}
for (int T = sta; T < (1 << m); T = (T + 1) | sta) {
bool flag = 0;
mems(vis, 0);
for (int k = 0; k < m; ++k) {
if ((S & T) & (1 << k)) {
vis[pm[j][k]] = 1;
}
}
for (int k = 0; k < m; ++k) {
if ((S & (1 << k)) && !vis[pm[j][k]]) {
flag = 1;
break;
}
}
if (flag) {
continue;
}
for (int k = 0; k < m; ++k) {
fa[k] = k;
}
for (int x = 0; x < m; ++x) {
for (int y = x + 1; y < m; ++y) {
if (pm[j][x] == pm[j][y] && (S & (1 << x)) && (S & (1 << y)) && (T & (1 << x)) && (T & (1 << y))) {
merge(x, y);
}
}
}
for (int k = 0; k + 1 < m; ++k) {
if ((T & (1 << k)) && (T & (1 << (k + 1)))) {
merge(k, k + 1);
}
}
for (int k = 0; k < m; ++k) {
g[k] = m;
}
for (int k = 0; k < m; ++k) {
int x = find(k);
g[x] = min(g[x], k);
}
vi v;
for (int k = 0; k < m; ++k) {
v.pb(g[find(k)]);
}
int nj = ID(v);
f[i][T][nj] = min(f[i][T][nj], f[i - 1][S][j] + __builtin_popcount(T ^ sta));
}
}
}
}
int ans = 1e9;
for (int S = 0; S < (1 << m); ++S) {
for (int i = 1; i <= ntot; ++i) {
if (f[R][S][i] > 1e9) {
continue;
}
int cnt = 0;
for (int j = 0; j < m; ++j) {
if (pm[i][j] == j && (S & (1 << j))) {
++cnt;
}
}
if (cnt == 1) {
ans = min(ans, f[R][S][i]);
}
}
}
printf("%d\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest Unite 296beginner atcoder contest 296 beginner atcoder contest unite 题解unite abc 296 contest programming beginner atcoder beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334