C++程序：查找非零子矩阵的数量

假设我们得到一个矩阵，其中只包含两个值：1 和 0。我们需要找到给定矩阵中包含全为 1 的子矩阵的数量。我们将输出该值。

因此，如果输入如下所示：

0010
0100
0101
1101

则输出将为 12。

为了解决这个问题，我们将遵循以下步骤：

  • n := 矩阵的大小
  • m := matrix[0] 的大小
  • 定义一个大小为 n+1 x m+1 的数组 add。
  • 初始化 i := 0，当 i < n 时，更新（i 加 1），执行：
    • 初始化 j := 0，当 j < m 时，更新（j 加 1），执行：
      • 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]
  • res := 0
  • 初始化 i := 0，当 i < n 时，更新（i 加 1），执行：
    • 初始化 j := 0，当 j < m 时，更新（j 加 1），执行：
      • 如果 matrix[i, j] 不为零，则：
        • 忽略以下部分，跳到下一次迭代
      • 初始化 k := 1，当 k <= (n - i) 时，更新（k 加 1），执行：
        • p := 0,
        • q := m - j;
        • 当 p <= q 时，执行：
          • x := (p + q) / 2
          • a := k * x
          • cur := add[i + k, j + x] - add[i, j + x] - add[i + k, j] + add[i, j]
          • 如果 cur 等于 a，则：
            • r := x
            • p := x + 1
          • 否则，
            • q := x - 1
        • 如果 r 等于 0，则：
          • 退出循环
        • res := res + r
  • 返回 res

示例

让我们看一下以下实现，以便更好地理解：

#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

更新于: 2021年10月16日

420 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告