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

সমস্যা বিবরণ

একটি ম্যাট্রিক্স এবং একটি টার্গেট মান দেওয়া থাকলে, আমাদের সেই ম্যাট্রিক্সের মধ্যে এমন নন-ইম্পটি সাবম্যাট্রিক্সের সংখ্যা বের করতে হবে যাদের উপাদানগুলোর যোগফল টার্গেটের সমান। এখানে একটি সাবম্যাট্রিক্স [(x1, y1), (x2, y2)] বলতে ম্যাট্রিক্সের সমস্ত সেল matrix[x][y] কে বোঝায়, যেখানে x1 থেকে x2 এবং y1 থেকে y2 পরিসরে থাকে। দুটি সাবম্যাট্রিক্স ভিন্ন হবে যদি তাদের কোনো একটি কোঅর্ডিনেট ভিন্ন হয়।

উদাহরণ

ইনপুট ম্যাট্রিক্স:

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

সমাধান পদ্ধতি

1. ans := 0
2. col := কলামের সংখ্যা, row := সারির সংখ্যা
3. প্রতিটি সারির জন্য প্রিফিক্স সাম গণনা করুন: matrix[i][j] += matrix[i][j-1]
4. একটি হ্যাশ ম্যাপ m সংজ্ঞায়িত করুন
5. সম্ভাব্য সব কলাম জোড়া (i, j) এর জন্য:
   • m ক্লিয়ার করুন, m[0] = 1, sum = 0
   • প্রতিটি সারি k এর জন্য:
     • current = matrix[k][j] - (i>0 ? matrix[k][i-1] : 0)
     • sum += current
     • ans += m[target - sum]
     • m[-sum]++
6. ans রিটার্ন করুন

C++ বাস্তবায়ন

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

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,1,0},{1,1,1},{0,1,0}};
    cout << ob.numSubmatrixSumTarget(v, 0);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {{0,1,0},{1,1,1},{0,1,0}}, 0

আউটপুট: 4