POJ 2724

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 #define maxn 2005
10 
11 int n,m,len,ans;
12 int ele[maxn],match[maxn];
13 vector<int> G[maxn];
14 bool vis[maxn];
15 
16 bool judge(int x1,int x2) {
17         int sum = 0;
18         for(int i = 0; i < 10; ++i) {
19                 if((x1 >> i & 1) ^ (x2 >> i & 1)) ++sum;
20         }
21 
22         return sum == 1;
23 }
24 void build() {
25     for(int i = 0; i < len; ++i) {
26             for(int j = i + 1; j < len; ++j) {
27                     if(judge(ele[i],ele[j])) {
28                             G[i].push_back(j);
29                             G[j].push_back(i);
30                     }
31             }
32     }
33 
34 }
35 
36 bool dfs(int u) {
37         for(int i = 0; i < G[u].size(); ++i ) {
38                 int v = G[u][i];
39                 if(vis[v]) continue;
40                 vis[v] = 1;
41                 if(match[v] == -1 || dfs(match[v])) {
42                         match[v] = u;
43                         return true;
44                 }
45         }
46 
47         return false;
48 }
49 
50 void solve() {
51 
52         for(int i = 0; i < len; ++i) G[i].clear();
53         build();
54 
55         for(int i = 0; i < len; ++i) {
56                 match[i] = -1;
57         }
58 
59         for(int i = 0; i < len; ++i) {
60                 memset(vis,0,sizeof(vis));
61                 if(dfs(i)) ++ans;
62         }
63 }
64 
65 int main()
66 {
67    // freopen("sw.in","r",stdin);
68     while(~scanf("%d%d",&n,&m)) {
69             len = 0;
70             ans = 0;
71             if(!n && !m) break;
72             char ch[20];
73             for(int i = 0; i < m; ++i) {
74                     scanf("%s",ch);
75                     int pos = -1,sum = 0;
76                     for(int j = 0; j < n; ++j) {
77                             if(ch[j] == ‘1‘)
78                                     sum += (1 << (n - j - 1));
79                             if(ch[j] == ‘*‘)
80                                     pos = n - j - 1;
81                     }
82 
83                     ele[len++] = sum;
84                     if(pos != -1) ele[len++] = sum + (1 << pos);
85 
86             }
87 
88             sort(ele,ele + len);
89             len = unique(ele,ele + len) - ele;
90 
91             solve();
92 
93             printf("%d\n",len - (ans / 2));
94     }
95 
96     return 0;
97 }