Submission #69491086

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;

int solve_one(int H, int W, const vector<string>& S) {
    // 黒マスに番号を割り当てる
    map<pair<int,int>, int> id;
    int idx = 0;
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            if(S[i][j] == '#'){
                id[{i,j}] = idx++;
            }
        }
    }
    int M = idx; // 黒マスの総数

    // 2x2 黒ブロックを列挙 bitmaskで高速化 
    // 黒マスは　最大49個?->uint64_t
    vector<uint64_t> blocks;
    for(int i=0; i+1<H; i++){
        for(int j=0; j+1<W; j++){
            if(S[i][j]=='#' && S[i][j+1]=='#' && S[i+1][j]=='#' && S[i+1][j+1]=='#'){
              uint64_t mask=0;
              mask |= 1ULL<<id[{i,j}];
              mask |= 1ULL<<id[{i,j+1}];
              mask |= 1ULL<<id[{i+1,j}];
              mask |= 1ULL<<id[{i+1,j+1}];
              blocks.push_back(mask);
            }
        }
    }
    if(blocks.empty()) return 0; // もともとOK

    int best = M; // 最悪は黒マス全部塗り替え

    // dfsで全パターン探索
    // bi:今処理しているブロック(2×2)の番号
    // used:これまでに白にしたマスの数
    function<void(int,uint64_t,int)> dfs = [&](int bi, uint64_t removed, int used){

        if(used >= best) return; // 剪定

        // used 個マスを白にした状態 -> 残り R 個のブロックが壊れていない
        // 奇跡的に「1 つのマスで 4 ブロック壊せる」状況が最大限続いたとしても
        // 最低でも ceil(R/4) 個は追加で塗らないと絶対壊せない
        // 今後どう頑張っても あと ceil(R/4) 個は絶対必要 -> used + ceil(R/4) 個以上
        // どうやってもこれ以上は改善できない -> 剪定
        int remaining=0;
        for(int k=bi; k<(int)blocks.size(); k++){
            if((blocks[k] & removed)==0) remaining++;
        }
        int lower=(remaining+3)/4;
        if(used+lower>=best) return;

        // すべて壊れてるならbest更新
        if(bi == (int)blocks.size()){
            best = min(best, used);
            return;
        }

        // このブロックがすでに壊れているなら次のブロックへ
        if(blocks[bi] & removed){
            dfs(bi+1, removed, used);
            return;
        }
        // 壊れていないなら、このブロックのどれかを白にする
        uint64_t mask=blocks[bi];
        for(int k=0; k<M; k++){
          if(mask>>k & 1ULL){
              dfs(bi+1,removed|(1ULL<<k),used+1);
          }
        }
    };

    dfs(0,0,0);
    return best;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int T; cin >> T;
  while(T--){
      int H, W; cin >> H >> W;
      vector<string> S(H);
      for(int i=0; i<H; i++) cin >> S[i];
      cout << solve_one(H,W,S) << "\n";
  }
  return 0;
}

Submission Info

Judge Result