Chương trình tìm số lượng ma trận con có tổng bằng giá trị mục tiêu trong C++

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

Ví dụ, nếu đầu vào là ma trận 4x4:

và target = 5, thì kết quả sẽ là 3.

Giải thuật

• n := kích thước của mat
• m := (n == 0 ? 0 : kích thước của mat[0])
• Nếu m > n:
  • Định nghĩa ma trận chuyển vị kích thước m x n
  • Điền chuyển vị: transpose[j][i] = mat[i][j]
  • Gọi đệ quy solve(transpose, sumTarget)
• ans := 0
• Vòng lặp p từ 0 đến m-1:
  • Định nghĩa mảng arr
  • Vòng lặp q từ p đến m-1:
    • Cập nhật arr[i] += mat[i][q] cho mọi i
    • Định nghĩa map pcnt với cặp {0, 1}
    • pref := 0
    • Vòng lặp i từ 0 đến n-1:
      • pref += arr[i]
      • Tìm tmp = pcnt.find(pref - sumTarget)
      • Nếu tmp != pcnt.end(): ans += tmp->second
      • pcnt[pref]++
• Trả về ans

Ví dụ minh họa

#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