uvaoj 11205: 这个题做了差不多2个半天。主要思路是： led能亮的根数可以为1-p根，对于每一种情况（比如能亮2根的情况）枚举可能亮的位置。用sy数组存储。 得到枚举的位置后，用sy与各个symbol求交集，也就是sy & symbol。相与的结果还是放在res矩阵中。 相与之后，判断res中有没有相同的行，如果有相同的行，则表明不成立。 最后，选取根数最小的数目。

gistfile1.cpp

#include <iostream>
#include <vector>
#include <string.h>
#include <fstream>
using namespace std;

void dfs(int *sy,vector<vector<int> > matrix,int n,int p,int cur,int &r){
    if(cur == p){//如果枚举到了i个。
        int res[n][p];
        memset(res, 0, sizeof(res));
        for(int i = 0; i < n; i++){//先把数据复制到res
            for(int j = 0; j < p; j++)
                res[i][j] = matrix[i][j];
        }
        for(int i = 0; i < n; i++){//用symbol中的数据和复制后的数据相与。
            for(int j = 0; j < p; j++)
                res[i][j] &= sy[j];//相与的结果放到res[][]中。
        }
        bool judge = true;
        for(int i = 0; i < n; i++){//判断相与的结果(res)是否相同。
            for(int j = i+1; j < n; j++){
                int same = 1;
                for(int k = 0; k < p; k++){
                    if(res[i][k] != res[j][k]){same = 0;break;}

                }
                if(same)//如果res的i行与j行都相同，但是matrix的i行与j行不相同。则表示这样亮灯不行。
                    {judge = false;break;}
            }
            if(!judge) break;
        }
        if(judge){
            int time = 0;
            for(int i = 0; i < p; i++)
                if(sy[i] == 1) time++;//统计数组中1的个数，也就是灯亮的个数。
            //if(time == 0)time++;//对于数组中所有值都为0的情况，
            if(time == 0)return;//sy数组中值都为0时，res中的各个值也都相同。但是这个结果并不是需要的。跳过。
            if(time < r)
                r = time;//记录所有情况中最小值。有没有办法直接跳出递归？
        }
        return;
    }
    sy[cur] = 0;
    dfs(sy,matrix,n,p,cur+1,r);
    sy[cur] = 1;
    dfs(sy,matrix,n,p,cur+1,r);
}

int main(){
    int num,p,n,symbol;
    vector<vector<int> > matrix;
    ifstream  fin;
    fin.open("D:\\C++\\test\\bin\\Debug\\123");
    fin>>num;//问题的个数
    while(num--){
        fin>>p>>n;//输入p(最多能亮的个数)；n(symbol的个数)
        matrix.clear();
        vector<int> vec;
        for(int i = 0; i < n; i++){
            vec.clear();
            for(int j = 0; j < p; j++){
                fin>>symbol;
                vec.push_back(symbol);
            }
            matrix.push_back(vec);//放到矩阵matrix中
        }//每个problem的数据先读到内存中
        int sy[p];//symbol是p维的。
        int r = 100,cur = 0;
        dfs(sy,matrix,n,p,cur,r);//i是每次最多能亮的数目。
        cout<<r<<endl;
       }
    return 0;
}