题解：AT_abc424_d [ABC424D] 2x2 Erasing 2

qdl66666666 · 2025-09-26 12:35:18 · 题解

题意

给定一个矩阵，每个格子为白色或黑色。每次我们可以使一个黑色格子变为白色，求使得矩阵中没有 2×2 的黑色子矩阵的最小操作数。

做法

注意到 h 和 w 最大为 7，考虑状压 DP。
设 f[s][i] 表示当前走到了第 i 行，当前行状态为 s 且满足在此行前不存在 2 × 2 的黑色子矩阵的最小操作次数。

可以存储每一行的初始状态 sit，预处理出每一行的合法状态 s，计算 sit 到 s 的黑格变化个数。

用上一行的状态来更新这一行的答案，按位比对判断两行状态是否满足不存在 2 × 2 黑色子矩阵。

复杂度 O(Twh2^w)

代码

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int T,h,w;
string s;
int sit[10],f[(1<<10)][10];
vector<pair<int,int> > e[10];
int sum(int x,int p){
    cerr<<x<<" "<<p<<")))\n";
    int sum = 0;
    for(int i=0;i<w;i++){
        if(!((x >> i) & 1) && !((p >> i) & 1)) sum++;
    }
    cerr<<sum<<"???\n";
    return sum;
}
bool check(int x,int y){
    for(int i=0;i<w;i++){
        if(((x >> i) & 3) == 3 && ((y >> i) & 3) == 3) return false;
    }
    return true;
}
void solve(){
    cin >> h >> w;
    for(int i=1;i<=h;i++){
        cin >> s;
        for(int j=0;j<s.size();j++){
            if(s[j]=='.') sit[i] += (1 << j);
        }
    }
    for(int i=1;i<=h;i++){
        for(int p=0;p<(1<<w);p++){
            f[p][i] = INT_MAX;
            if(!(sit[i] & p)) e[i].push_back({p,sum(sit[i],p)});
        }
    }
    for(auto x : e[1]){
        f[x.fi][1] = x.se;
    }
    for(int i=2;i<=h;i++){
        for(auto x : e[i]){
            for(auto y : e[i - 1]){
                if(check(x.fi,y.fi)){
                    f[x.fi][i] = min(f[x.fi][i],f[y.fi][i-1] + x.se);
                }
            }
        }
    }
    int ans = INT_MAX;
    for(auto x : e[h]){
        ans = min(ans,f[x.fi][h]);
    }
    cout << ans << "\n";
    memset(sit,0,sizeof sit);
    for(int i=1;i<=9;i++){
        e[i].clear();
    }
}
int main(){
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}