Chương trình để tìm ra số lượng ma trận con từ một ma trận trong đó tổng các phần tử bằng một giá trị cụ thể trong C ++

Giả sử chúng ta được cung cấp một ma trận có chứa các giá trị nguyên. Chúng ta phải tìm ra ma trận con từ ma trận mà tổng các phần tử của ma trận bằng một giá trị tổng mục tiêu đã cho. Chúng tôi trả về số lượng ma trận con.

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

và target =5, thì đầu ra sẽ là 3.

Số lượng ma trận con có tổng các phần tử bằng 6 là 2.

Để 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 tấm thảm
• m:=(nếu n giống 0 thì 0, nếu không thì kích thước của tấm lót [0])
• nếu m> n, thì -
  • Xác định một mảng 2D hoán vị các kích thước m x ​​n
  • để khởi tạo i:=0, khi i
  • để khởi tạo j:=0, khi j
  • chuyển vị [j, i]:=mat [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>>& mat, int sumTarget) {
   int n = mat.size();
   int m = n == 0 ? 0 : mat[0].size();

   if (m > n) {
      vector<vector<int>> transpose(m, vector<int>(n));
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            transpose[j][i] = mat[i][j];
         }
      }
      return solve(transpose, sumTarget);
   }

   int ans = 0;
   for (int p = 0; p < m; p++) {
      vector<int> arr(n);
      for (int q = p; q < m; q++) {
         for (int i = 0; i < n; i++) {
            arr[i] += mat[i][q];
         }

         unordered_map<int, int> pcnt = {{0, 1}};
         int pref = 0;
         for (int i = 0; i < n; i++) {
            pref += arr[i];
            auto tmp = pcnt.find(pref - sumTarget);
            if (tmp != end(pcnt)) ans += tmp->second;
            pcnt[pref]++;
         }
      }
   }
   return ans;
}

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, 5) <<endl;
return 0;
}

Đầu vào

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

Đầu ra

3