UVa11205 The Broken Pedometer

// 题意：有P个LED灯，以及N个字符，要求选出个数最少的LED灯，使得即使只有这些灯正常工作，也能区分出这N个字符
// 题意抽象：输入两个整数P, N以及N行P列的01矩阵，找少的列，能区分所有行
// 规模：P<=15, N<=100
// 算法：2^P枚举。把每行理解为二进制整数可以简化代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<string>

#include<algorithm>

#include<set>

using namespace std;

const int P=15;

const int N=100;

int p,n;

//bits

int buf[N];

set<int> s;

bool judge(int x)

{

        s.clear();

        for(int i=0;i<n;i++)

        {

                int k=x & buf[i];

                if(s.find(k)!=s.end())

                {

                        return false;

                }

                s.insert(k);

        }

        return true;

}

int count_bits(int x)

{

        int cnt=0;

        for(int i=0;i<p;i++)

        {

                if(x&(1<<i))

                        cnt++;

        }

        return cnt;

}

int main()

{

#ifndef ONLINE_JUDGE

        freopen("./uva11205.in", "r", stdin);

#endif

        int T;

        scanf("%d", &T);

        while(T--)

        {

                memset(buf, 0, sizeof buf);

                scanf("%d %d", &p, &n);

                for(int i=0;i<n;i++)

                        for(int j=0;j<p;j++)

                        {

                                int b;

                                scanf("%d", &b);

                                buf[i]|=(b<<j);

                        }

                int ans=P;

                for(int i=0;i<(1<<p);i++)

                {

                        if(judge(i))

                        {

                                int t=count_bits(i);

                                if(t<ans)

                                        ans=t;

                        }

                }

                printf("%d\n", ans);

        }

    return 0;

}