Số lượng ma trận con tổng để nhắm mục tiêu trong C ++

Giả sử chúng ta có một ma trận và một giá trị đích, chúng ta phải tìm số lượng ma trận con không rỗng mà tổng đó giống với giá trị đích. Ở đây, submatrix [(x1, y1), (x2, y2)] là tập hợp tất cả các ô ma trận [x] [y] với x trong phạm vi x1 và x2 và y trong phạm vi y1 và y2. Hai ma trận con [(x1, y1), (x2, y2)] và [(x1 ', y1'), (x2 ', y2')] khác nhau nếu chúng có một số tọa độ khác nhau:như, nếu x1 thì không giống như x1 '.

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

và target =0, thì đầu ra sẽ là 4, điều này là do bốn ma trận con 1x1 chỉ chứa 0.

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

• ans:=0

• col:=số cột

• row:=số hàng

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=1, khi j

    • matrix [i, j]:=matrix [i, j] + matrix [i, j - 1]

• Xác định một bản đồ m

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=i, khi j

    • xóa bản đồ m

    • m [0]:=1

    • tổng:=0

  • để khởi tạo k:=0, khi k

    • hiện tại:=matrix [k, j]

    • nếu tôi - 1> =0, thì -

      • current:=current - matrix [k, i - 1]

    • sum:=sum + hiện tại

    • ans:=ans + m [target - sum]

    • tăng m [-sum] lên 1

• trả lại ans

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int numSubmatrixSumTarget(vector<vector<int>>& matrix, int
   target) {
      int ans = 0;
      int col = matrix[0].size();
      int row = matrix.size();
      for(int i = 0; i < row; i++){
         for(int j = 1; j < col; j++){
            matrix[i][j] += matrix[i][j - 1];
         }
      }
      unordered_map <int, int> m;
      for(int i = 0; i < col; i++){
         for(int j = i; j < col; j++){
            m.clear();
            m[0] = 1;
            int sum = 0;
            for(int k = 0; k < row; k++){
               int current = matrix[k][j];
               if(i - 1 >= 0)current -= matrix[k][i - 1];
               sum += current;
               ans += m[target - sum];
               m[-sum]++;
            }
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,0},{1,1,1},{0,1,0}};
   cout << (ob.numSubmatrixSumTarget(v, 0));
}

Đầu vào

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

Đầu ra

4