Poj Solution 2724

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

#include <memory.h>
#include <stdio.h>
#include <string.h>


#define null 0
const int size = 2010;
bool e[size][size];

int maxmatch( int n, int m, bool w[][size], int *p)
{

    int p_n[size];
    int p_m[size];

    bool sign[size];
    int q[size],from[size],s,t;

    int i,j,link,now,h;

    memset( p_n, -1, sizeof(int)*n );
    memset( p_m, -1, sizeof(int)*m );

    for(i=0;i<n;i++)
    if(p_n[i]==-1)
    {
        memset( sign, 0, sizeof(bool)*m );
                
        s=1;link=-1;
        from[0]=-1;

        q[0]=size-1;
        p_m[size-1]=i;

        for(t=0;t<s;t++)
        {
           now=q[t];
           for(j=0;j<m;j++)
           {
               if( w[p_m[now]][j] != null && sign[j]==0 )
               {
                    sign[j]=1;
                    q[s]=j;
                    from[s++]=t;

                    if(p_m[j]==-1)
                    {
                        link=s-1;
                        break;
                    }
               }
           }
           if(j<m)break;
        }

        if(t<s)
        {
             while(from[link]!=-1)
             {
                    h=from[link];
                    p_m[q[link]]=p_m[q[h]];
                    p_n[p_m[q[h]]]=q[link];
                    link=h;
             }
        }

    }
    int an;

    for(i=0,an=0;i<n;i++)
    {
        if(p)p[i]=p_n[i];
        if(p_n[i]>=0)an++;
    }
    return an;
}

char s[2010][11];

int check( char *a, char *b ) {
    int i;
    for( i=0; a[i] && a[i] == b[i]; i++ )
        ;
    if( !a[i] )
        return 2;
    for( i++; a[i] && a[i] == b[i]; i++ )
        ;
    return !a[i];
}

int h;

void add( char *w, int key ) {
    int k;

    for( k=0; k<h; k++ )
        if( check( s[k], w ) == 2 )
            return;

    for( k=0; k<h; k++ )
        if( check( s[k], w ) ) {
            if( key )
                e[k][h] = 1;
            else
                e[h][k] = 1;
        }

    if( k == h )
        strcpy( s[h++], w );
}

int main() {
    int n, m, i, k, c;
    char *cp;
    char w[11];

    while( scanf("%d%d", &m, &n ) == 2 && n >0 && m > 0 ) {
        h = 0;
        memset( e, 0, sizeof e );

        for( i=0; i<n; i++ ) {
            scanf( "%s", w );

            c = 0;
            for( k=0; w[k]; k++ )
                if( w[k]=='1' )
                    c++;

            cp = strchr( w, '*' );
            if( cp ) {
                *cp = '0';
                add( w, c%2 );
                *cp = '1';
                add( w, (c+1)%2 );
            }
            else {
                add( w, c%2 );
            }
        }
        printf( "%dn", h-maxmatch( h, h, e, 0 ) );
    }
    return 0;
}