ধরা যাক একটি ম্যাট্রিক্স দেওয়া আছে যাতে পূর্ণসংখ্যা মান রয়েছে। আমাদের এমন সাবম্যাট্রিক্স বের করতে হবে যাদের উপাদানগুলোর যোগফল একটি দেওয়া টার্গেট সমানের সমান। সাবম্যাট্রিক্সের সংখ্যা রিটার্ন করতে হবে।
উদাহরণস্বরূপ, ম্যাট্রিক্স = {{0,0,1,0},{0,1,0,0},{0,1,0,1},{1,1,0,1}} এবং target = 5 হলে আউটপুট হবে ৩।
নোট: মূল টেক্সটে "sum of elements is equal to 6" বলা হয়েছে, কিন্তু ইনপুটে target 5 দেওয়া আছে। সঠিক আউটপুট ৫ টার্গেটের জন্য ৩।
সমাধানের ধাপসমূহ
- n := ম্যাট্রিক্সের সাইজ (রো)
- m := কলামের সাইজ (যদি n=0 হয় তবে ০)
- যদি m > n হয়, তবে ম্যাট্রিক্স ট্রান্সপোজ করে সমস্যা সমাধান করুন
- ans := ০
- প্রতিটি কলাম p = 0 থেকে m-1 পর্যন্ত:
- আকার n-এর একটি অ্যারে arr সংজ্ঞায়িত করুন
- q = p থেকে m-1 পর্যন্ত:
- প্রতিটি রো i এর জন্য arr[i] += mat[i][q] করুন
- একটি ম্যাপ pcnt তৈরি করুন যাতে {0, 1} থাকে
- pref := ০
- প্রতিটি রো i = 0 থেকে n-1 পর্যন্ত:
- pref += arr[i]
- যদি (pref - sumTarget) pcnt-এ থাকে, তবে ans += pcnt[pref - sumTarget]
- 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আউটপুট
3
