AOJ 1128 : Square Carpets

問題リンク:Square Carpets | Aizu Online Judge

問題概要：
最大10*10のマスがあり、それらの中には０か１が書かれている
値が１であるようなマスを全てカーペットで覆いたい
カーペットは正方形で、長さは自由に決めれる
ただしカーペットで覆うマスの値は全て１でなければならない
全ての１のマスを覆うためにはカーペットは最小で何枚必要か

解法：
枝刈り探索で頑張る
前処理として、
各マスを左上として置けるカーペットの最大の一辺の長さを求める
次に先程きめたカーペットをすべて置いたとき、１枚のカーペットにしか覆われないようなマスをみつけ、そこにはあらかじめカーペットをしいておく（置かなければそこをカバーできないため
まだカバーされていないマスの数を数える
__builtin_popcountを前処理で求めておく

ここまでしたらDFSで探索を開始する
マスを１つ１つ見ていき、そこのマスにカーペットを敷くか敷かないかで探索する
現時点で分かっている最小のカーペット枚数と現在使ったカーペット枚数+(まだカーペットが残っているのであれば1,それ以外は０)が同じかそれ以上なのであれば処理をやめる
カーペットを敷いたが、別のカーペットの上に完全に重なるように敷いてしまった場合も処理を止める
カーペットを敷く処理はビットで行う
以上

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int IINF = INT_MAX;
int H,W,mincost;
int P[10][10],bin[10],bc[(1<<10)];
int put[10][10],counter[10][10];

bool can_put(int len,int x,int y){
  REP(i,y,y+len)REP(j,x,x+len) if( !P[i][j] ) return false;
  return true;
}

void dfs(int cur,int cost,int remain){

  if( cost >= mincost ) return;
  if( cost + ((remain>0)?1:0) >= mincost ) return;

  if( cur >= H*W ) {
    mincost = min(mincost,cost);
    return;
  }

  int x = cur % W, y = cur / W;

  if( !P[y][x] || counter[y][x] == 1 ) {
    dfs(cur+1,cost,remain);
    return;
  }

  if( (bin[y]>>x) & 1 ) dfs(cur+1,cost,remain);

  int len = put[y][x];
  int bitmask = ((1<<len)-1)<<x;
  int buf[len];
  int add = 0, nremain = remain;
  rep(j,len) {
    buf[j] = bin[y+j];
    add += len - bc[((1<<len)-1)&(bin[y+j]>>x)];
    bin[y+j] |= bitmask;
  }
  nremain -= add;
  if( add ) dfs(cur+1,cost+1,nremain);
  rep(j,len) bin[y+j] = buf[j];

}

bool isValid(int x,int y){ return 0 <= x && x < W && 0 <= y && y < H; }

int main(){

  rep(i,(1<<10)) bc[i] = __builtin_popcount(i);

  while( scanf("%d%d",&W,&H), W | H ){

    rep(i,H){
      bin[i] = 0;
      rep(j,W){
        cin >> P[i][j];
        put[i][j] = 0;
      }
    }
    rep(y,H) rep(x,W) if( P[y][x] ) {
      for(int len=min(H,W);len>=1;len--){
        if( x + len - 1 < W && y + len - 1 < H ) {
          if( can_put(len,x,y) ){
            put[y][x] = len;
            break;
          }
        }
      }
    }

    rep(i,H)rep(j,W) counter[i][j] = 0;
    rep(i,H)rep(j,W)if(P[i][j]){
      REP(y,i,i+put[i][j])REP(x,j,j+put[i][j]){
        counter[y][x]++;
      }
    }

    rep(i,H){
      rep(j,W){
        if( counter[i][j] == 1 ){
          REP(y,i,i+put[i][j])REP(x,j,j+put[i][j]){
            bin[y] |= (1<<x);
          }
        }
      }
    }

    int add = 0;
    int remain = 0;
    mincost = 0;
    rep(i,H)rep(j,W)remain += ((bin[i]>>j)&1),mincost += P[i][j];
    remain = mincost - remain;
    dfs(0,0,remain);

    rep(i,H)rep(j,W)if(counter[i][j]==1)add++;
    cout << mincost+add << endl;

  }
  return 0;
}