C++中求非零子矩阵个数的程序

假设我们有一个只包含两个值的矩阵;1 和 0。我们必须找出给定矩阵中包含全 1 的子矩阵的数量。我们将值打印为输出。

所以,如果输入是这样的

0010
0100
0101
1101

那么输出将是 12。

示例

让我们看看以下实现以获得更好的理解 -

#include<bits/stdc++.h>

using namespace std;

int solve(vector<vector<int>>& matrix) {

   int n = matrix.size();

   int m = matrix[0].size();

   int add[n + 1][m + 1];

   memset(add, 0, sizeof(add));

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

      for (int j = 0; j < m; j++) {

         add[i + 1][j + 1] += matrix[i][j];

         add[i + 1][j + 1] += add[i][j + 1];

         add[i + 1][j + 1] += add[i + 1][j];

         add[i + 1][j + 1] -= add[i][j];

      }

   }

   int res = 0;

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

      for (int j = 0; j < m; j++) {

         if (!matrix[i][j])

            continue;

         for (int k = 1; k <= (n - i); k++) {

            int p = 0,

               q = m - j;

            int r;

            while (p <= q) {

               int x = (p + q) / 2;

               int a = k * x;

               int cur = add[i + k][j + x] - add[i][j + x] - add[i + k][j] + add[i][j];

               if (cur == a) {

                  r = x;

                  p = x + 1;

               } else

                  q = x - 1;

            }

            if (r == 0)

               break;

            res += r;

            }

      }

   }

   return res;

}

int main() {

   vector<vector<int>> mat = {{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}};

cout<< solve(mat) <<endl;

return 0;

}

输入

{{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}}
输出结果
12

以上是 C++中求非零子矩阵个数的程序 的全部内容, 来源链接: utcz.com/z/335411.html

回到顶部