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