C++ में मैट्रिक्स से विशिष्ट योग वाले सबमैट्रिक्स की संख्या ज्ञात करने का प्रोग्राम

मान लीजिए हमें एक मैट्रिक्स दिया गया है जिसमें पूर्णांक मान हैं। हमें मैट्रिक्स से उन सबमैट्रिक्स को ढूंढना है जिनके तत्वों का योग दिए गए लक्ष्य योग के बराबर है। हम ऐसे सबमैट्रिक्स की संख्या लौटाते हैं।

उदाहरण के लिए, यदि इनपुट मैट्रिक्स है:

0	0	1	0
0	1	0	0
0	1	0	1
1	1	0	1

और target = 5, तो आउटपुट 3 होगा।

नोट: मूल पाठ में "sum of elements is equal to 6" लिखा है लेकिन आउटपुट 3 दिया गया है target 5 के लिए। यह टाइपो प्रतीत होता है।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

n := mat का आकार
m := (यदि n == 0 तो 0 अन्यथा mat[0] का आकार)
यदि m > n:
- आयाम m x n का एक 2D सरणी transpose परिभाषित करें
- i := 0 से n-1 तक:
  - j := 0 से m-1 तक:
    - transpose[j][i] := mat[i][j]
- solve(transpose, sumTarget) लौटाएं
ans := 0
p := 0 से m-1 तक:
- एक सरणी arr परिभाषित करें
- q := p से m-1 तक:
  - i := 0 से n-1 तक:
    - arr[i] := arr[i] + mat[i][q]
  - एक मैप pcnt परिभाषित करें जिसमें {0, 1} हो
  - pref := 0
  - i := 0 से n-1 तक:
    - pref := pref + arr[i]
    - tmp := pcnt में (pref - sumTarget) की स्थिति खोजें
    - यदि tmp pcnt के अंत के बराबर नहीं है:
      - ans += tmp->second
    - pcnt[pref]++
ans लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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

इनपुट

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