読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 1128 : Square Carpets

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

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

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

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

コード:

#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;
}