C++程序 计算二进制矩阵中1和0的集合数

给定一个n × m的二进制矩阵，计算其中一个集合可以由一行或一列中的一或多个相同值组成的数量。

示例:

输入: 1 0 1
0 1 0
输出: 8
说明: 有六个单一元素集合(三个1和三个0)，还有两个两个元素的集合，第一个集合由第一行的第一个和第三个单元格组成，
第二个集合由第二行的第一个和第三个单元格组成。

输入: 1 0
1 1
输出: 6

x个元素的非空子集的数量为2 x – 1。我们遍历每一行，计算1和0单元格的数量。对于u个0和v个1，总集合的数量是2 u – 1 + 2 v – 1。然后，我们遍历所有列，计算相同值并计算总和。最后，我们从总和中减去m x n，因为单个元素被计算两次。

// CPP program to compute number of sets// in a binary matrix.#include <bits/stdc++.h>using namespace std; const int m = 3; // no of columnsconst int n = 2; // no of rows // function to calculate the number of// non empty sets of celllong long countSets(int a[n][m]){      //存储最终答案    long long res = 0;         //按行遍历    for (int i = 0; i < n; i++)    {        int u = 0, v = 0;        for (int j = 0; j < m; j++)            a[i][j] ? u++ : v++;                 res += pow(2,u)-1 + pow(2,v)-1;    }         //按列遍历    for (int i = 0; i < m; i++)    {        int u = 0, v = 0;        for (int j = 0; j < n; j++)             a[j][i] ? u++ : v++;         res += pow(2,u)-1 + pow(2,v)-1;    }         //最后减去n*m，因为单一的集合被计算两次。    return res-(n*m);} // driver program to test the above function.int main() {         int a[][3] = {(1, 0, 1),                  (0, 1, 0)};         cout << countSets(a);         return 0;}  

输出:

8

时间复杂度: O(n * m)

空间复杂度: O(1)，因为没有额外的空间被使用。