সাবম্যাট্রিসের সংখ্যা যা C++ এ টার্গেট করে

ধরুন আমাদের একটি ম্যাট্রিক্স এবং একটি লক্ষ্য মান আছে, আমাদেরকে অ-খালি সাবম্যাট্রিসের সংখ্যা খুঁজে বের করতে হবে যেগুলির যোগফল টার্গেটের সমান। এখানে একটি সাবম্যাট্রিক্স [(x1, y1), (x2, y2)] হল সমস্ত সেল ম্যাট্রিক্সের সেট [x][y] যার রেঞ্জ x1 এবং x2 এবং y রেঞ্জ y1 এবং y2। দুটি সাবমেট্রিস [(x1, y1), (x2, y2)] এবং [(x1', y1'), (x2', y2')] আলাদা হয় যদি তাদের কিছু স্থানাঙ্ক থাকে যা ভিন্ন:যেমন, যদি x1 না হয় x1' এর মতই।

সুতরাং, যদি ইনপুট মত হয়

এবং টার্গেট =0, তাহলে আউটপুট হবে 4, এর কারণ হল চারটি 1x1 সাবমেট্রিস যাতে শুধুমাত্র 0 থাকে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• উত্তর :=0

• col :=কলামের সংখ্যা

• সারি :=সারির সংখ্যা

• আরম্ভ করার জন্য i :=0, যখন i

  • j শুরু করার জন্য :=1, যখন j করুন

    • ম্যাট্রিক্স[i, j] :=ম্যাট্রিক্স[i, j] + ম্যাট্রিক্স[i, j - 1]

• একটি মানচিত্র m

  সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • j শুরু করার জন্য :=i, যখন j করুন

    • ম্যাপ সাফ করুন m

    • m[0] :=1

    • যোগফল :=0

  • আরম্ভ করার জন্য k :=0, যখন k <সারি, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন −

    • বর্তমান :=ম্যাট্রিক্স[কে, জে]

    • যদি i - 1>=0, তাহলে −

      • বর্তমান :=বর্তমান - ম্যাট্রিক্স[k, i - 1]

    • যোগফল :=যোগফল + বর্তমান

    • ans :=ans + m[লক্ষ্য - যোগফল]

    • 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