Saratov State University Online Contester 527 Explode 'Em All

練習会復習。

問題概要

nxmマスのグリッドがある。
'.'は何もないマスで、'*'は石のあるマスである。
i行j列に爆弾を落とすと、同じ行の石全ておよび同じ列の石全てが破壊される。
全ての石を破壊するのに必要な爆弾の最小の数を求めよ。


n,m≦25

解法

一見フローっぽいがフローでは解けない。
総当りも無理っぽいので、枝刈りをがんばって探索したらTLE.


実は前処理をすることによって総当りで解くことが可能になる。
左半分、右半分に分けてそれぞれの半分で、
ビット列iで表される列の集合に爆弾を落としたときに石が残る行のビットを
left[i], right[i]として計算しておく。


半分全列挙みたいな前処理をするというのが面白い。

ソースコード

int bit[1<<25];

void run()
{
	int h,w; cin>>h>>w;
	char f[25][26];
	rep(i,h)cin>>f[i];
	
	int left[1<<12], right[1<<13];
	rep(i,1<<25){
		int cnt=0;
		for(int j=i;j;j&=j-1)cnt++;
		bit[i]=cnt;
	}
	rep(i,1<<w/2){
		left[i]=0;
		rep(j,w/2)if(!(i&1<<j))rep(k,h)if(f[k][j]=='*')left[i]|=1<<k;
	}
	rep(i,1<<w-w/2){
		right[i]=0;
		rep(j,w-w/2)if(!(i&1<<j))rep(k,h)if(f[k][j+w/2]=='*')right[i]|=1<<k;
	}
	
	int ans=25;
	rep(i,1<<w){
		int lbit=i&(1<<w/2)-1, rbit=i>>w/2;
		ans=min(ans,max(bit[i],bit[left[lbit]|right[rbit]]));
	}
	cout<<ans<<endl;
}