#include <iostream>
using namespace std;
#define N 1100
#define M 1100
bool map[N][M];
int match[M];
bool chk[M];
int n, m;
bool num[1100];
int hash[1100];
int dfs(int p)
{
int i,t;
for(i=1; i<=m; i++)
{
if(!chk[i] && map[p][i] )
{
chk[i]=1;
t=match[i];
match[i]=p;
if(t == -1 || dfs(t) ) return 1;
match[i]=t;
}
}
return 0;
}
int maxMah()
{
int i, ans=0;
for(i=1; i<=n; i++)
{
memset(chk, 0, sizeof(chk));
if(dfs(i)) ans++;
}
return ans;
}
int getnum(char *s)
{
int i,ret=0, l=strlen(s);
for(i=0; s[i]; i++)
{
ret+= (s[i]=='1'?(1<<(l-i-1)):0);
}
return ret;
}
int main()
{
int x,y, i, j, k, c;//,ans=0;
char tmp[15];
while(scanf("%d%d", &x, &y)!=EOF && x!=0 && y!=0 )
{
memset(map, 0, sizeof(map));
memset(num,0, sizeof(num));
memset(hash,0, sizeof(hash));
memset(match, -1, sizeof(match));
for(i=0; i<y; i++)
{
scanf("%s",tmp);
for(j=0; tmp[j]; j++)
if(tmp[j]=='*')
break;
if(tmp[j])
{
tmp[j]='0';
num[ getnum(tmp) ] =true ;
tmp[j]='1';
num[ getnum(tmp) ] =true ;
}
else num[ getnum(tmp) ] =true ;
}
for(i=0, k=0; i<(1<<x); i++)
if(num[i])
{
hash[++k]=i;
}
for(i=1; i<=k; i++)
for(j=1; j<=k; j++)
{
c=hash[i]^hash[j];//判是否相差一位
if(c && ((c&(c-1))==0) )//判是否相差一位
map[i][j]=map[j][i]=1;
}
n=m=k;
printf("%d\n",k-maxMah()/2); //(k-maxMah)+maxMah/2=k-maxMah()/2
}
return 0;
}
posted on 2010-03-25 01:23
wyiu 閱讀(466)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ