POJ-2032, AOJ-1128 : Square Carpets

問題概要

10*10の盤面があり、各マスは黒か白である。任意の大きさの正方形で全ての黒いマスを被覆する。このとき、はみ出したり白のマスに重なってはいけない。最小枚数を求める問題。

解法

基本方針はBBだけど、下界は相当緩くてよい。正方形を考えるときは他の正方形に含まれるようなものを除去して極大なものだけを候補とし、候補の中で1枚でしかカバーされないようなマスは確定させてよいとかであまり探索空間は広くならない。

acceptされたコード

#include <cstdio>
#include <cstring>
#include <bitset>
#include <vector>
using namespace std;

const int MAX_W = 10;
const int MAX = MAX_W * MAX_W;

typedef bitset<MAX> bit;

bit mask;
int W, H;
int board[MAX_W][MAX_W];
int accum[MAX_W + 1][MAX_W + 1];
int best;

bool included(const bit& a, const bit& b){
	return (a&b) == a;
}

bool init(){
	scanf("%d%d", &W, &H);
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			scanf("%d", board[i]+j);
		}
	}
	return H > 0;
}

void dfs(int score, bit brd, vector<bit> bs){
	for(int i=0; i<H*W; ++i)if(!brd[i]){
		int cnt = 0, key = -1;
		for(int j=0; j<(int)bs.size(); ++j){
			if(bs[j][i]){
				++cnt;
				key = j;
			}
		}
		if(cnt == 1){
			++score;
			brd |= bs[key];
		}
	}

	if(brd == mask){
		best = min(best, score);
		return ;
	}

	if(score >= best - 1){
		return ;
	}

	for(int i=0; i<(int)bs.size(); ++i){
		bs[i] &= mask & (~brd);
	}

	vector<bit> ts;
	for(int i=0; i<(int)bs.size(); ++i)if(bs[i].any()){
		for(int j=i+1; j<(int)bs.size(); ++j){
			if(bs[i]==bs[j]){
				bs[j].reset();
			}
		}
	}

	for(int i=0; i<(int)bs.size(); ++i){
		bool ok = true;
		for(int j=0; j<(int)bs.size(); ++j)if(i!=j){
			if(included(bs[i], bs[j])){
				ok = false;
				break;
			}
		}
		if(ok){
			ts.push_back(bs[i]);
		}
	}

	for(int i=0; i<(int)ts.size(); ++i){
		bit t = ts[i];
		ts[i].reset();
		dfs(score+1, brd | t, ts);
		ts[i] = t;
	}
}

int solve(){
	mask.reset();
	for(int i=0; i<W*H; ++i){
		mask.set(i, true);
	}
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			accum[i+1][j+1] = accum[i+1][j] + accum[i][j+1] - accum[i][j] + (1 - board[i][j]);
		}
	}

	bit brd;
	vector<bit> bs;
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			if(board[i][j] == 0){
				brd.set(i*W+j);
			}
			else{
				int sz = 0;
				for(int k=1; i+k<=H && j+k<=W; ++k){
					if(accum[i+k][j+k] - (accum[i+k][j] + accum[i][j+k]) + accum[i][j] == 0){
						sz = k;
					}
				}
				bit bt;
				for(int a=0; a<sz; ++a){
					for(int b=0; b<sz; ++b){
						bt.set((i+a)*W+(j+b), true);
					}
				}
				bs.push_back(bt);
			}
		}
	}

	vector<bit> ts;
	for(int i=0; i<(int)bs.size(); ++i){
		bool ok = true;
		for(int j=0; j<(int)bs.size(); ++j)if(i!=j){
			ok &= !included(bs[i], bs[j]);
		}
		if(ok){
			ts.push_back(bs[i]);
		}
	}

	best = MAX;
	dfs(0, brd, ts);

	return best;
}

int main(){
	for(;init();){
		printf("%d\n", solve());
	}

	return 0;
}