Chương trình tìm ra số lượng ma trận con khác 0 trong C ++

Giả sử chúng ta được cho một ma trận chỉ chứa hai giá trị; 1 và 0. Chúng ta phải tìm ra số lượng ma trận con trong ma trận đã cho có chứa tất cả các số 1. Chúng tôi in giá trị dưới dạng đầu ra.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 12.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của ma trận
• m:=kích thước của ma trận [0]
• Xác định kích thước bổ sung mảng:n + 1 x m + 1.
• để khởi tạo i:=0, khi i
• để khởi tạo j:=0, khi j
• thêm [i + 1, j + 1] + =ma trận [i, j]
• thêm [i + 1, j + 1] + =thêm [i, j + 1]
• thêm [i + 1, j + 1] + =thêm [i + 1, j]
• thêm [i + 1, j + 1] - =thêm [i, j]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

{{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}}

Đầu ra

12