POJ 3740 - Easy Finding

http://poj.org/problem?id=3740

概要

要素が 0 か 1 である M * N の行列が与えられる． 「どの列にも1が一度しか表れない」ようにいくつかの行を選ぶことができるかどうかを答える．

例えばサンプルの場合，

0 1 0
0 0 1
1 0 0

は1行目から3行目までを選べばよく，

0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0

はどのように行を選んでも条件を満たすことができない．

制約

• M <= 16
• N <= 300

解法

行の選び方は高々 2^16 通りしかないので適当に枝を刈りながら DFS．

 1 #include <cstdio>
 2 #include <bitset>
 3 using namespace std;
 4 
 5 int M, N;
 6 static const int MAXM = 300;
 7 bitset<MAXM> a[16];
 8 
 9 bool dfs(const bitset<MAXM>& s, unsigned used, int from)
10 {
11   if (s.count() == N) {
12     return true;
13   }
14   for (int i = from; i < M; i++) {
15     if (!(used & (1<<i)) && (s & a[i]) == 0) {
16       if (dfs(s | a[i], used | (1<<i), i+1)) {
17         return true;
18       }
19     }
20   }
21   return false;
22 }
23 
24 int main()
25 {
26   while (scanf("%d %d", &M, &N) != EOF) {
27     for (int i = 0; i < M; i++) {
28       a[i].reset();
29       for (int j = 0; j < N; j++) {
30         int x;
31         scanf("%d", &x);
32         a[i].set(j, x != 0);
33       }
34     }
35 
36     puts(dfs(0, 0, 0) ?  "Yes, I found it" : "It is impossible");
37   }
38   return 0;
39 }