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

मान लीजिए कि हमारे पास एक मैट्रिक्स है, और एक लक्ष्य मूल्य है, हमें गैर-रिक्त सबमैट्रिसेस की संख्या का पता लगाना है जो योग लक्ष्य के समान है। यहां एक सबमैट्रिक्स [(x1, y1), (x2, y2)] सभी सेल मैट्रिक्स [x] [y] का सेट है, जिसमें x रेंज x1 और x2 और y रेंज y1 और y2 में है। दो सबमैट्रिस [(x1, y1), (x2, y2)] और [(x1', y1'), (x2', y2')] अलग हैं यदि उनके पास कुछ निर्देशांक हैं जो अलग हैं:जैसे, यदि x1 नहीं है X1' के समान।

तो, अगर इनपुट पसंद है

और लक्ष्य =0, तो आउटपुट 4 होगा, ऐसा इसलिए है क्योंकि चार 1x1 सबमैट्रिस जिसमें केवल 0 होता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• उत्तर:=0

• col :=स्तंभों की संख्या

• पंक्ति :=पंक्तियों की संख्या

• इनिशियलाइज़ करने के लिए:=0, जब मैं <पंक्ति, अपडेट (i 1 से बढ़ाएँ), करें -

  • इनिशियलाइज़ j :=1 के लिए, जब j

    • मैट्रिक्स [i, j]:=मैट्रिक्स [i, j] + मैट्रिक्स [i, j - 1]

• एक नक्शा परिभाषित करें मी

• इनिशियलाइज़ करने के लिए मैं :=0, जब i

  • इनिशियलाइज़ j :=i के लिए, जब j

    • नक्शा साफ़ करें मी

    • मी[0] :=1

    • योग :=0

  • k :=0 को इनिशियलाइज़ करने के लिए, जब k <रो, अपडेट (k को 1 से बढ़ाएँ), करें -

    • वर्तमान:=मैट्रिक्स [के, जे]

    • अगर मैं - 1>=0, तो -

      • करंट:=करंट - मैट्रिक्स [k, i - 1]

    • योग :=योग + वर्तमान

    • उत्तर:=उत्तर + एम [लक्ष्य - योग]

    • m[-sum] को 1 से बढ़ाएं

• वापसी उत्तर

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

उदाहरण

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

इनपुट

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

आउटपुट

4