2397. 被列覆盖的最多行数-深度优先枚举+二进制检索

2397. 被列覆盖的最多行数-深度优先枚举+二进制检索

给你一个下标从 0 开始的 m x n 二进制矩阵 mat 和一个整数 cols ，表示你需要选出的列数。

如果一行中，所有的 1 都被你选中的列所覆盖，那么我们称这一行 被覆盖 了。

请你返回在选择 cols 列的情况下，被覆盖 的行数 最大 为多少。

示例 1：

输入：mat = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], cols = 2
输出：3
解释：
如上图所示，覆盖 3 行的一种可行办法是选择第 0 和第 2 列。
可以看出，不存在大于 3 行被覆盖的方案，所以我们返回 3 。

示例 2：

输入：mat = [[1],[0]], cols = 1
输出：2
解释：
选择唯一的一列，两行都被覆盖了，原因是整个矩阵都被覆盖了。
所以我们返回 2 。

解题代码如下：

int max_count;


void find_max(int *a,int tra,int m){
   
    int count=0;
    for(int i=0;i<m;i++){
        if((a[i]&tra)==0){
            count++;
        }
       


    }
    max_count=fmax(max_count,count);
  //  printf("count %d ",count);
 
}

void dfs(int data,int cols,int now,int n,int po,int *a,int m){
    if(po==cols){
      
        find_max(a,data,m);

    }
    else{
         for(int i=now;i<n;i++){
           
             dfs(data-pow(2,i),cols,i+1,n,po+1,a,m);

         }

    }
   

}

int maximumRows(int** matrix, int matrixSize, int* matrixColSize, int numSelect){
    int m=matrixSize,n=matrixColSize[0];
    int* a=(int *)malloc(sizeof(int)*matrixSize);
    int* r=(int *)malloc(sizeof(int)*matrixSize);

    for(int i=0;i<m;i++){
        a[i]=0;
        r[i]=1;
        int p=1;
        for(int j=n-1;j>=0;j--){
             a[i]=a[i]+p*matrix[i][j];
             p=p*2;

        }
    }
   max_count=0;
   
    int num=pow(2,n)-1;
     dfs(num,numSelect,0,n,0,a,m);

    


    
    return max_count;

}