PKU演習問メモ(4/11)

No. Title 分類・解法 主観的難易度
3740 Easy Finding DFS, Bit operation ★★☆☆☆


体調悪い。

3740 Easy Finding

問題概要

各成分が0または1がのMxN行列(M≦16, N≦300)がある。この行列のうちいくつかの行を選んで、各列に1がちょうど一つだけ現れるようにすることができるか判定せよ。

解法

選ぶMについて深さ優先探索で書いてみた。……んだけど2^16総当りでやったほうが計算量少ないっぽい?orz
M行を全部一つの数にまとめることで判定にかかる計算量が1/16になる。

ソースコード
int h,w;
int mtx[300];
bool one[300];

bool rec(int cur)
{
	if(cur==h)
	{
		rep(i,w)if(!one[i])return 0;
		return 1;
	}
	
	bool ok=1;
	rep(i,w)if(one[i]&&(mtx[i]&1<<cur))
	{
		ok=0; break;
	}
	if(ok)
	{
		rep(i,w)one[i]^=!!(mtx[i]&1<<cur);
		if(rec(cur+1))return 1;
		rep(i,w)one[i]^=!!(mtx[i]&1<<cur);
	}
	
	return rec(cur+1);
}

int main()
{
	while(~scanf("%d%d",&h,&w))
	{
		fill(mtx,mtx+w,0);
		rep(i,h)rep(j,w)
		{
			int t; scanf("%d",&t);
			if(t)mtx[j]|=1<<i;
		}
		fill(one,one+w,0);
		cout<<(rec(0)?"Yes, I found it":"It is impossible")<<endl;
	}
	return 0;
}